The solution of recurrence relation T(n) = 2T(√n) + log(n) is
2018
The solution of recurrence relation
T(n) = 2T(√n) + log(n)
is
- A.
O(log(n) log(log(n)))
- B.
O(log(n) log(n))
- C.
O(n log(n))
- D.
O(log(n))
Attempted by 74 students.
Show answer & explanation
Correct answer: A
Let n = 2^m, implying log(n) = m. The recurrence transforms to S(m) = 2S(m/2) + m. Applying the Master Theorem yields Theta(m log m). Substituting back gives O(log n log log n).
A video solution is available for this question — log in and enroll to watch it.