Arrange the following recurrence relations in increasing order of their time complexity.

(A) $T(n) = T(n/2) + 1$

(B) $T(n) = 2T(n/2) + n$

(C) $T(n) = 3T(n/3) + n$

(D) $T(n) = 2T(n/2) + \sqrt{n}$

(E) $T(n) = T(n-1) + 1$

Using Master Theorem / recurrence expansion:

(A)
$T(n) = T(n/2) + 1$
Complexity → $O(\log n)$

(E)
$T(n) = T(n-1) + 1$
Complexity → $O(n)$

(D)
$T(n) = 2T(n/2) + \sqrt{n}$

$n^{\log_2 2} = n$

Since $\sqrt{n} < n$

→ $O(n)$

(B)
$T(n) = 2T(n/2) + n$

$n^{\log_2 2} = n$

→ $O(n \log n)$

(C)
$T(n) = 3T(n/3) + n$

$n^{\log_3 3} = n$

→ $O(n \log n)$

Increasing order

$O(\log n) < O(n) < O(n) < O(n\log n) < O(n\log n)$