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