Ask
Login
2
30kviews
Which are the different methods of solving recurrences? Explain with example.
written 8.8 years ago by gravatar for teamques10 teamques10 ★ 70k •   modified 5.7 years ago
analysis of algorithms
ADD COMMENT EDIT
1 Answer
5
1.4kviews
written 8.8 years ago by gravatar for teamques10 teamques10 ★ 70k

There are mainly three ways for solving recurrences.

1) Substitution Method: We make a guess for the solution and then we use mathematical induction to prove the the guess is correct or incorrect.

For example consider the recurrence T(n) = 2T(n/2) + n

We guess the solution as T(n) = …

Create a free account to keep reading this post.

and 4 others joined a min ago.

ADD COMMENT EDIT
Please log in to add an answer.