Solutions to problems in recursion analysis

Click here for the questions

1. Using the substitution method, we substitute the function recursively till we arrive at T(1).
   i.e T(n)=T(n/2) + 1 = T(n/4) + 1 + 1 = ....
   
   We get a total of lg(n) iterations
   i.e T(n)=T(1) +lg(n)
   
   Thus the complexity is O(lg n).
   


2. Similar to the 1st problem, it takes lg(n) iterations to reach T(1).After final iteration:
   
   T(n)=(2^lg(n))*(T(1) + lg(n)*17)
   
   Thus the complexity is (2^lg(n))*(lg n) = n*lg(n)
   


3. Let n=2^m,then T(2^m)=2*T(2^m/2) + 1
   Now let S(m)=T(2^m).
   =>S(m)=2*S(m/2) +1
   
   This is the same as 2nd problem.
   Thus the complexity is O(m*lg(m)),but m=lg(n)
   
   Thus the final complexity is O(lg(n)*lg(lg(n)))