Mathematics Homework Solutions
Problem
#49076

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

Solution
What is this?
By OTA - Overall OTA Rating
Purchase Cost Now
$2.19 CAD (was ~$3.99)
Included in Download
  • Plain text response
  • Attached file(s):
    • proof.doc
$2.19 Instant Download
Add to Cart
Why you can trust BrainMass.com
  • Your Information is Secure
  • Best Online Academic Help Service
  • Students find real academic Success
Related Solutions
Browse