For each of the following recurrences, find a tight upper bound for T(n). It will be...

  

Transcribed Image Text:

For each of the following recurrences, find a tight upper bound for T(n). It will be useful to remember that Wi j=0 1 1 a , if |a| < 1. Prove that each is correct using induction. In each case, assume that T(n) is constant for n < 2. (a) T(n) = 2T (n/2) + n (b) T(n) = T(9n/10) + n (c) T(n) = 7T(n/3) + n2 (d) T(n) =T(n) +1 (e) T(n) = T(n - 1) + lgn For each of the following recurrences, find a tight upper bound for T(n). It will be useful to remember that Wi j=0 1 1 a , if |a| < 1. Prove that each is correct using induction. In each case, assume that T(n) is constant for n < 2. (a) T(n) = 2T (n/2) + n (b) T(n) = T(9n/10) + n (c) T(n) = 7T(n/3) + n2 (d) T(n) =T(n) +1 (e) T(n) = T(n - 1) + lgn