Share
Explore BrainMass

Proof

I received the following proof, can someone show all steps of how the solution was formed?

Proof:

Let n=2^2^k, then we have
T(n)=T(2^2^k)=2T(n^(1/2))+log n

***How do you get n^(1/2) equals 2^2^(k-1)

=2T(2^2^(k-1))+2^k

***How do you get 2T(2^2^(k-1)) equals 2(2T(2^2^(k-2))+2^(k-1))

=2(2T(2^2^(k-2))+2^(k-1))+2^k
=2^2*T(2^2^(k-2))+2*2^k
=2^2*(2T(2^2^(k-3))+2^(k-2))+2*2^k
=2^3*T(2^2^(k-3))+3*2^k
=...
=2^k*T(2^2^0)+k*2^k
=2^k*T(2)+k*2^k
=2^k+k*2^k
=(k+1)*2^k
Since n=2^2^k, then 2^k=lg n and k=lg lg n
Thus T(n)=theta((lg n)*(lg lg n))

***Please show intermediate steps

$2.19