Recursion Analysis

Recursion algorithms can be analysed by 3 methods : Substitution method,recursion tree method and master method.

1)Show that the solution of T(n)=T(n/2) + 1 is O(lg n).

2)Show that the solution to T(n)=2*T((n/2)+17) is O(n*(lg n)).

3)Solve the recurrence T(n)=2*T(sqrt(n)) + 1.

4)Use a recursion tree to determine a good asymptotic upper bound on the recurrence T(n)=3*T(n/2) + n.

5)Use a recursion tree to give an asymptotically tight solution to the recurrence T(n)=T(n-a) + T(a) +cn,where a >=1 and c>0 are constants.

6)Draw the recursion tree for t(n)=4T(n/2)+cn,where c is a constant,and provide a tight asymptotic bound on its solution.

7)Use a recursion tree to give an asymptotically tight solution to the recurrence T(n)=T(an)+T((1-a)n)+cn,where a is a constant in the range 0<>0 is also a constant.

8)Use master method to give tight asymptotic bounds for the following recurrences.
a.T(n)=4T(n/2)+n.
b.T(n)=4T(n/2)+n^3

9)The recurrence T(n)=7T(n/2)+n^2 describes the running time of an algorithm A.A completing algorithm A' has a running time of T'(n)=aT'(n/4)+n^2.What is the largest integer value for a such that A' is asymptotically faster than A?

10)Can the master method be applied to the recurrence T(n)=4T(n/2)+n^2(lg n)? Why or why not? Give an asymptotic upper bound for this recurrence.

11)Use the master method to show that the solution to the binary-search recurrence T(n)=T(n/2)+ Theta(1) is T(n)=Theta(lg n).

Click here for the solutions

Find some problems on recursion here