time complexity

Question

find TC  : $T(n)= 2T(\sqrt{n}) + 1$

Comments

back substitution:

T(n)=2T(n^1/2) +1-----(1)

(n^1/2)=2T(n^1/4) +1----(2)

put 2 in 1

=2²T(n^1/4) +2.(1)

=2^kT(n^{1/(2)^k}) +k.1-----(3)

here

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

      2^k=log n

     k=log log n

from 3=>

           =log n .C +log log n .1

T(n)  = ⊖( log n)..

Answer 1

T(n) = 2T(√n) + 1

assume n = 2^k

T(2^K) = 2T(2^k)^1/2 + 1

T(2^K) = 2T(2^k/2)+ 1

assume T(2^K)  = S(K)

S(K)  = 2S(K/2) + 1

apply extended master theorem 1

a = 2  b = 2 

S(K)= K^LOG₂2

S(K)= ⊖(K¹

but S(K)=T(2^K)

T(2^K) = ⊖(K¹ )

but n = 2^k

K = Logn

so, putting value  we, get

T(n)  = ⊖( logn) is answer....

Comments

How you write

2T(2^k/2) = 2S(k/2) ????

If T(2^k)=S(k)

Then it should 2S(k^1/2)

Please explain it

---

Yes

---

They assumed T(2^k)=S(k)  And here k/2 is there

       therefore  T(2^k/2)=S(k/2);

Answer 2

The terms will be like this:

1 +2 + 4 + 8.......$2^{loglogn}$

= theta(logn)