Solutions to problems in recursion analysis

• 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).
  
• 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)
  
• 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)))