in Algorithms retagged by
523 views
0 votes
0 votes

$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)$
in Algorithms retagged by
523 views

2 Answers

3 votes
3 votes
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) $

4 Comments

And what if T(n)=T(√n)+c
0
0
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.
0
0
But according to masters theorem here there is no 'a' (a≻=1)
0
0
Here 'a' = 1 bro. $T(n) = 1\times T(\sqrt{n}) + c$
0
0
0 votes
0 votes

o(logn)

Related questions