2. For the following recurrences, use the recursion tree method to find a good guess of...

 

Transcribed Image Text:

2. For the following recurrences, use the recursion tree method to find a good guess of what they solve to asymptotically (i.e. in big-Oh notation). Assume T(1) = 1. (a) T(n) = 3T(n/3) + n for n > 1. (b) T(n) = 4T(n/2) + n for n > 1. 3. Consider the following runtime recurrence: T(1) = 1 and T(n) = 3T(n/2) + n when n > 2. Use big-Oh induction to prove that T(n) O(n). 2. For the following recurrences, use the recursion tree method to find a good guess of what they solve to asymptotically (i.e. in big-Oh notation). Assume T(1) = 1. (a) T(n) = 3T(n/3) + n for n > 1. (b) T(n) = 4T(n/2) + n for n > 1. 3. Consider the following runtime recurrence: T(1) = 1 and T(n) = 3T(n/2) + n when n > 2. Use big-Oh induction to prove that T(n) O(n).

Answer rating: 100% (QA)

The image contains two questions regarding recurrence relations one of which asks to use the recursion tree method to find a good guess of what they solve to asymptotically and the other asks to prove ... View the full answer