Question

Consider the reccurence function
T(n) = { 2T($\sqrt{n}$) + 1, n > 2
2, 0 < n $\le$ 2
Then T(n) in terms of $\ominus$ notation is

• A. $\Theta$(log n)
• B. $\Theta$(n)
• C. $\Theta$(log log n)
• D. $\Theta$($\sqrt{n}$)

Answer 1

The correct option is B $\Theta$(n)

T(n) = 2T ($\sqrt{n}$) + 1 ... (1)
T(n) = 2T ($\sqrt[2]{2n}$) +1 ..... (2)
Substituting (2) in (1)
T(n) = 2.2T($\sqrt[2]{2n}$) + 2
T(n) = $2^2$T ($\sqrt[2]{2n}$) + 2 ..... (3)
T($\sqrt[2]{2n}$) = 2T ($\sqrt[3]{3n}$) + 1 ...... (4)
Substituting (4) in (3)
T(n) = $2^3$T ($\sqrt[3]{3n}$) + 3
Running the same till K times.
T(n) = $2^K$ T($\sqrt[K]{Kn}$) + K
$\sqrt[K]{Kn}$ = 2
K = $lo{g}_2$ n
Solving this will give
T(n) = $\Theta$(log n)