#algorithm

Question

Comments

@Gabbar (B) should be right.

---

how to solve it??

Answer 1

$\color{olive}{T(n) = 2T(\sqrt{n}) + log(n)}$

Let $\color{navy}{n = 2^m}$, and putting this in above recurrence relation.

$T(2^m) = 2T(2^{\frac{m}{2}}) + m$

Let, $S(m) = T(2^m)$, then, $S(\frac{m}{2}) = T(2^\frac{m}{2})$

$S(m) = 2S(\frac{m}{2}) + m$

This is similar to Merge-Sort (or) using master's theorem, it can be said that $S(m) = O(mlog_{2}(m))$

Now. replacing $m$ by $log_{2}(n)$, $\color{red}{T(n) = O(log_{2}(n)log_{2}log_{2}(n))}$

Comments

that Tricky step i'm not getting ??

---

and instead of 2^m-1 there should be 2^(m/2)

---

Updated:)

Answer 2

$\color{red}{T(\sqrt{n})}$ always gives us $\log \log n $ level in the recursion tree and in this particular question each level has equal work which is $\log n$.

Total work = net complexity = $\log n . \log \log n$ = $O(\log n . \log \log n)$

Comments

but in question,it is given at N=2..

---

Given that, $T(1) = 1$, and you start with $T(n)$

Then you take square_root, again and again, to reach n=1 and stop there.

But you can not reach an exact decimal value of 1 without taking floor value.

So, $$\begin{align*}\left \lfloor n^{\frac{1}{2^{k}}} \right \rfloor =1 \end{align*}$$ , but not the exact value.

We need to recurse up to $$\begin{align*} n^{\frac{1}{2^k}} = 2 \end{align*}$$ and in the next level STOP.

---

and we take termination @ n =2 (or @ n = 1.9999999999)