Which of the following is correct solution of the given recurrence relation?…
2026
Which of the following is correct solution of the given recurrence relation? T(n) = 3T(n/4) + n log n
θ(n log n)
θ(n2 log n)
θ(n (log n)2)
θ(n log log n)
- A.
1
- B.
2
- C.
3
- D.
4
Attempted by 114 students.
Show answer & explanation
Correct answer: A
Solution
Step 1: Identify parameters from T(n) = 3T(n/4) + n log n. Here a = 3, b = 4, and f(n) = n log n.
Step 2: Calculate n^log_b a = n^log_4 3. Since log_4 3 is approximately 0.79, n^log_4 3 is roughly n^0.79.
Step 3: Compare f(n) with n^log_b a. The function n log n grows polynomially faster than n^0.79.
Step 4: Check regularity condition. 3(n/4)log(n/4) is less than c * n log n for c < 1. This confirms Case 3 applies.
Step 5: Conclude T(n) = Theta(f(n)) = Theta(n log n).