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

Answer: A. O(log(n) log(log(n))) — 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…

  1. A.

    O(log(n) log(log(n)))

  2. B.

    O(log(n) log(n))

  3. C.

    O(n log(n))

  4. D.

    O(log(n))

Attempted by 191 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.

Explore the full course: Coding For Placement

Loading lesson…