Arrange the following recurrence relations in increasing order of their time…

Compute time complexity for each recurrence:

• T(n) = T(n/2) + 1 → Θ(log n). Reason: a = 1, b = 2 ⇒ n^{log_b a} = 1, f(n) = Θ(1), so T(n) = Θ(log n).

• T(n) = T(n-1) + 1 → Θ(n). Reason: this recurrence adds 1 for each decrement, summing to Θ(n).

• T(n) = 2T(n/2) + n → Θ(n log n). Reason: a = 2, b = 2 ⇒ n^{log_b a} = n, f(n) = Θ(n), so T(n) = Θ(n log n).

• T(n) = 3T(n/3) + n → Θ(n log n). Reason: a = 3, b = 3 ⇒ n^{log_b a} = n, f(n) = Θ(n), so T(n) = Θ(n log n).

Order from smallest to largest growth:

1. T(n) = T(n/2) + 1 — Θ(log n)

2. T(n) = T(n-1) + 1 — Θ(n)

3. T(n) = 2T(n/2) + n — Θ(n log n)

4. T(n) = 2T(n/2) + n — Θ(n log n) (same asymptotic as previous)

5. T(n) = 3T(n/3) + n — Θ(n log n) (same asymptotic class)

Thus the increasing order by time growth is: T(n) = T(n/2) + 1, then T(n) = T(n-1) + 1, followed by the three Θ(n log n) recurrences. Any permutation of the Θ(n log n) recurrences is asymptotically equivalent.