Consider the following recurrence:
Which one of the following is true?
(A) T(n) = 
(loglogn)
(B) T(n) = (logn)
(C) T(n) = (sqrt(n))
(D) T(n) = (n)
(A) A
(B) B
(C) C
(D) D
Answer: (B)
Explanation: This question can be solved by first change of variable and then Master Method.
Let n = 2^m T(2^m) = T(2^(m/2)) + 1 Let T(2^m) = S(m) S(m) = 2S(m/2) + 1
Above expression is a binary tree traversal recursion whose time complexity is (m). You can also prove using Master theorem.
S(m) =(m) =
Now, let us go back to the original recursive function T(n)
T(n) = T(2^m) = S(m)
= (Logn)
Whether you’re preparing for your first job interview or aiming to upskill in this ever-evolving tech landscape, neveropen Courses are your key to success. We provide top-quality content at affordable prices, all geared towards accelerating your growth in a time-bound manner. Join the millions we’ve already empowered, and we’re here to do the same for you. Don’t miss out – check it out now!
