#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

What is the significance of floor function here??

---

simply it avoids fractions ; and for large n , asymptotically no of levels and work in each level does not change significantly.

---

@Debashish right! but Inorder to find upper bound, floor can be ignored.

---

If ceil fn then also same ans??

---

Yes.

---

can you pls explain how log ( n^1/2) has log log n levels??

---

actualy ,for getting number of levels,i am not able to solve 

n^{(1/2) ^k}  = 1

^{what is the value of k in terms of n ,where k are the number of levels and 'n' are no. of elements}

---

$\begin{align*} &\text{ assume terminating consition at n = 2} \\ &\Rightarrow n^{\frac{1}{2^k}} = 2 \\ &\Rightarrow \frac{1}{2^k}.\log n = 1 \\ &\Rightarrow \log n = 2^k \\ &\Rightarrow k = \log \log n \\ \end{align*}$

---

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)