Algorithms | Analysis of Algorithms (Recurrences) | Question 11

Namachila 11 minutes ago

0 0 1 minute read

Consider the following recurrence.

T(n) = T( $\sqrt{n}$ ) + $\Theta(Log Log n)$

What is the value of recurrence?

(A) $\Theta( (Log Log n) ^ 2)$
(B) $\Theta(Log Log n)$
(B) $\Theta(n)$
(B) $\Theta(Log Log Log n)$

(A) A
(B) B
(C) C
(D) D

Answer: (A)
Explanation: Change of variables: let m = lg n. Recurrence becomes S(m) = S(m/2) + theta(lgm). Case 2 of master’s theorem applies, so T(n) = theta( (log Log n) ^ 2).
Quiz of this Question

Whether you’re preparing for your first job interview or aiming to upskill in this ever-evolving tech landscape, zambiatek 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!