Problem set 3   --- Solutions
                                      
A. Notice first that the y parameter is the only one that plays a role 
in the running time, as the termination condition and the changes of 
values apply only to it. We get

                     3                          if y = 0     

T(y)  =              7+ T(y/2)            if y>0 and y is even
                 
                      9 + T ((y-1)/2)    if y>0 and y is odd

To see that this is the correct relation, notice that the case y=0 is just 
counting the operations (condition, comparison and return operations). If 
y is bigger than 0 we simply count the operations for each one of the
corresponding cases. Notice that for the third case we have to count all 
operations of the first two cases other then the return operations.
  
                 
B. We have T(y) = 7 + T(y/2) = 7 + 7 + T(y/4) = .... 7i + T(y/2^i) = 
(setting i to log y) 7 log y + T(1) =  7 log y + 9 + T(0) = 7 logy + 12
  We prove this by induction: P(k) = "  T(2^k) == 7k+ 12 "
  
  check P(0): T*1) = 9 + T(0) = 12. Hence P(0) holds.
  For some k>=0 assume P(k) and show P(k+1) (simple induction): 
   T(2^{k+1)) = 7 + T(2^k) = 7 + 7k + 12 = 7(k+1) + 12 so P(k+1) holds.
   
   C. Notice that if y is a number which is a power of 2 minus 1 (like 
      3,7,15...) then throughout the recursion the third case (y odd) will 
      always be used, except when y is becomes 0. Since there is cost of 9 
      for this case in addition to the time to apply the recursion, it seems 
      that this will represent the worst case. We will first check the running
       time for such a number. 
    
   T(2^k-1) = 9+ T(2^{k-1}-1) + 9 + ( + T(2^{k-1}-1) = .....  9 k + T(0)= 
     9k+ 3. This allows us to guess T(y) <= 9 log (y+1) + 3.
     T(0) = 3 = 9 log (0 + 1) + 3
     if y > 0 is even 
      T(y) = 7 + T((y/2) <= 7 + 9 log (y/2+1) + 3 <= 10 + 9 (log (y+2) - 1) = 
        1 + 9 log (y+2) <= 3 + 9 log (y+1)
     if y > 0 is odd 
      T(y) = 9 + T ((y-1)/2) = 9 + (9 log ((y+1)/2) + 3 = 9 log (y+1) + 3
    
    So we have proven the upper bound. By part B we can conclude 
     T(y) = Theta(log n).