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

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

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

ReplyDeletePlease find the updated link for solutions. we will put more solutions to this post asap.

ReplyDeleteplease answer all questions

ReplyDelete7)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.

ReplyDeletesolution for que 5?

ReplyDeletewhat would be the solution to number 4?

ReplyDeleteT(n)=T(an)+T(1-n)a+cn

ReplyDeleteplese answer this recursion

Great and Useful Article.

ReplyDeleteJava Online Training

Online Java Course

Java Course Online

J2EE training

online J2EE training

Best Recommended books for Spring framework

Java Interview Questions

Java Training Institutes in Chennai

Java Training in Chennai

J2EE Training in Chennai

java j2ee training institutes in chennai

Java Course in Chennai