Question

Let T(n) denote the worst case running time of an algorithm when its input has size n. In divide and conquer algorithms, T(n) is often expressed using a recursion. Hence, expressing T(n) in terms of the big-Oh notation requires a bit of work. There are many ways of determining the growth rate of T(n). In class, I’ve shown you how to do it by drawing the recursion tree. Here are the steps: (1) draw the recursion tree out, (2) determine the non-recursive work that is done at each level, and then (3) add them all up. The final step often involves analyzing a geometric sum of the form 1 + a + a 2 + . . . + a r . Recall that if a < 1, this sum is O(1); if a = 1, this sum is equal to O(r); if a > 1, this sum is O(a r ).

Using steps 1, 2, and 3, determine the growth rate of T(n) using the big-Oh notation for each of the cases below. a. T(n) = 5T(n/2) + O(n) b. T(n) = 3T(n/3) + O(1) c. T(n) = T(n/2) + O(n 2 )

Answer 1