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

come up with an algorithm

Let T[1..n] be a sorted array of distinct integers, some of which may be negative. Give an algorithm that can find an index i such that 1 <= i <= n and T[i] = i, provided such an index exists. Your algorithm should take a time in Big "O" (log n) in worst case.

Solving Recurrence Relations/Difference Equations

See attached file for full problem description.

Proof of binary search tree

Prove that any binary search algorithm on a sorted array of size n that uses only key comparisons must require at least omega (log n) comparisons in the worst case.

Proof: tree contains a cycle

Prove that a graph with n nodes and more than n-1 edges must contain at least one cycle.