edited by
210 views

1 Answer

1 votes
1 votes
$$
T(n)=\Theta(\log \log n)
$$
To see this, note that $\underbrace{\sqrt{\ldots \sqrt{n}}}_{i \text { times }}=n^{1 / 2^{i}}$. So, once $i$ becomes $\log \log n$ we will have $n^{1 / 2^{i}}=n^{1 / \log n}=1$. Thus the recursion stops after $\log \log n$ levels and each level contributes $1 ,$ hence $T(n)=\Theta(\log \log n)$.
Answer:

Related questions