time complexity

Question

$t(n)= 2t(\sqrt n) +c $;  if $n>2$

$\qquad =1$;  if $n<=2$

1.  $O(logn n)  $
2. $O(log log n)$
3. $O(nlog n)$
4. $O(n)$

Answer 1

In such questions, to take advantage of Master Theorem, we need to reduce the recurrence into some other form to which Master Theorem is applicable.

Given, $T(n) = 2T(\sqrt{n}) + c$

Put $n = 2^{m}$  in the equation

$T(2^m) = 2T(2^{m/2}) + c$

Now let's assume $P(m) = T(2^m) $

So, recurrence becomes $P(m) = 2P(\frac{m}{2}) + c$

Now, applying Master Theorem to this recurrence, we get

$P(m) = \theta (m^{log_{2}2}) = \theta(m)$

 

So, $T(2^m) = P(m) = \theta(m) $

Substituting for m, $m = log_{2}n$

$T(2^{log_{2}n}) = \theta(log_{2}n) $

which implies that $T(n) = \theta(log_{2}n) $

Comments

And what if T(n)=T(√n)+c

---

Follow the same procedure and you will get the simplified recurrence relation as

$P(m) = P(m/2) + c$

On solving it through Master Theorem, you'll get
$P(m) = \theta(n^{log_{2}1}log(m)) = \theta(log(m)))$

Now you can convert m into n as done in the above example.

---

But according to masters theorem here there is no 'a' (a≻=1)

---

Here 'a' = 1 bro. $T(n) = 1\times T(\sqrt{n}) + c$

Answer 2

o(logn)