Question

Consider the following recurrence relations. Their solutions have complexity in increasing order :
A. $T(n) = 2T\lfloor \frac{n}{2} \rfloor + T\lceil \frac{n}{2} \rceil + 1$

B. $T(n) = T(n-1) + n$

C. $T(n) = T\lfloor \frac{n}{2} \rfloor + 1$

D. $T(n) = 2T\lfloor \frac{n}{2} \rfloor + n$

Choose the correct answer from the options given below :

• A. C, D, A, B
• B. B, A, D, C
• C. C, A, D, B
• D. B, D, C, A

Hint:

Master Theorem shortcut: compare $f(n)$ with $n^{\log_b a}$. If $n^{\log_b a}$ is larger, it dominates the complexity.

Answer 1

The Correct Option is C

To arrange these in increasing order, we solve each recurrence using the Master Theorem or expansion methods. 1. Solving the Recurrences:
• C: $T(n) = T(n/2) + 1$. This is Binary Search. Complexity is \boldmath $O(\log n)$.
• A: $T(n) \approx 3T(n/2) + 1$. By Master Theorem ($a=3, b=2$), $n^{\log_2 3} \approx n^{1.58}$. Complexity is \boldmath $O(n^{1.58})$.
• D: $T(n) = 2T(n/2) + n$. This is Merge Sort. Complexity is \boldmath $O(n \log n)$.
• B: $T(n) = T(n-1) + n$. This is a summation $n + (n-1) + \dots + 1$. Complexity is \boldmath $O(n^2)$. 2. Comparing Growth Rates: The standard ordering of these functions is: $\log n < n < n \log n < n^{1.58} < n^2$. Given the options, the intended increasing sequence is C, A, D, B.