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

9 comments:

  1. The solutions link doesn't work do you think you can fix this? Thanks

    ReplyDelete
  2. sorry,we also didn't observe this. give me 2 mins time to fix this.

    ReplyDelete
  3. Please find the updated link for solutions. we will put more solutions to this post asap.

    ReplyDelete
  4. please answer all questions

    ReplyDelete
  5. 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.

    ReplyDelete
  6. solution for que 5?

    ReplyDelete
  7. what would be the solution to number 4?

    ReplyDelete
  8. T(n)=T(an)+T(1-n)a+cn
    plese answer this recursion

    ReplyDelete