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\lceil \frac{n}{2} \rceil + 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:

Compare the solutions: C is log n, D is n log n, A is about n^1.58, B is n^2.

Answer 1

The Correct Option is A

Step 1: Understanding the Question:

We have to arrange four recurrences in increasing order of the growth of their solutions.

Step 2: Detailed Explanation:

• C: \( T(n) = T(n/2) + 1 \) gives \( \Theta(\log n) \).

• D: \( T(n) = 2T(n/2) + n \) gives \( \Theta(n \log n) \) by the Master theorem.

• A: \( T(n) \approx 3T(n/2) + 1 \) gives \( \Theta(n^{\log_2 3}) \approx \Theta(n^{1.58}) \).

• B: \( T(n) = T(n-1) + n \) gives \( \Theta(n^2) \).

• Increasing order: \( \log n < n \log n < n^{1.58} < n^2 \), i.e. C, D, A, B.

Step 3: Final Answer:
The correct option is (A) C, D, A, B.