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

Concept:
• Recurrence relations define the time complexity of recursive algorithms.
• We solve these using the Master Theorem or recursive tree methods to find their asymptotic bounds (Big-O notation).

Step 1: Solve Relation C
\(T(n) = T(n/2) + 1\).
This is characteristic of Binary Search.
By Master Theorem (\(a=1, b=2, d=0\)), since \(a = b^d\) (\(1 = 2^0\)), the complexity is \(O(\log n)\).

Step 2: Solve Relation D
\(T(n) = 2T(n/2) + n\).
This is characteristic of Merge Sort.
By Master Theorem (\(a=2, b=2, d=1\)), since \(a = b^d\) (\(2 = 2^1\)), the complexity is \(O(n \log n)\).

Step 3: Solve Relation A
\(T(n) \approx 3T(n/2) + 1\).
By Master Theorem (\(a=3, b=2, d=0\)), since \(a > b^d\) (\(3 > 1\)), the complexity is \(O(n^{\log_2 3}) \approx O(n^{1.58})\).

Step 4: Solve Relation B
\(T(n) = T(n-1) + n\).
This is the sum of the first \(n\) integers: \(n + (n-1) + (n-2) + \dots + 1 = \frac{n(n+1)}{2}\).
The complexity is \(O(n^2)\).

Step 5: Compare and Order
Comparing the growth rates: \(\log n < n \log n < n^{1.58} < n^2\).
Order: C \(\rightarrow\) D \(\rightarrow\) A \(\rightarrow\) B.