Consider the recurrence function \(T(n) = \begin{cases} 2T(\sqrt{n})+1, & n>2…
2017
Consider the recurrence function
\(T(n) = \begin{cases} 2T(\sqrt{n})+1, & n>2 \\ 2, & 0 < n \leq 2 \end{cases}\)
Then \(T(n)\) in terms of \(\Theta\) notation is
- A.
\(\Theta(\log \log n)\) - B.
\(\Theta( \log n)\) - C.
\(\Theta (\sqrt{n})\) - D.
\(\Theta(n)\)
Attempted by 77 students.
Show answer & explanation
Correct answer: B
Key idea: convert the recursion into levels and count work per level.
Let L be the number of times we take square roots until the size drops to at most 2: n^{1/2^L} \u2264 2. Taking logs gives 2^L \u2265 log_2 n, so L = Theta(log log n).
At level i there are 2^i subproblems, each contributing O(1) from the +1 term, so level i cost = Theta(2^i).
Total cost = sum_{i=0}^{L} Theta(2^i) = Theta(2^L).
Since 2^L = Theta(log n), we get T(n) = Theta(log n).
Therefore, T(n) = Theta(log n).
A video solution is available for this question — log in and enroll to watch it.