Assignment 2
Due September 25, 2019

Use proof by induction to verify the following claims.

a.  R(n) = 3R(n/4) + 2R(n/8) + n if n >= 8 and R(n) = 1 if n <8; 
       
      (i) Verify whether R(n) <= c n for any constant c
      (ii) Verify whether R(n) <= c n log n for some constant c
      (iii) Verify whether R(n) >= c n for some constant c

b.  R(n) = 4R(n/2) + n*n if n >= 2; R(n) = 1 if n = 1;
       
       (i) Verify whether R(n) <= c n*n for some c
       (ii) Verify whether R(n) >= d n*n for some d