Recurrence Relationships

आपका स्वागत हैं| मैं हूँ प्रोफेस्सर रिद्द्ले...

Professor : In the last class, I told you about Asymptotic notations. In this class, we shall study how to solve recurrence relationships. You have already come across a recursive algorithm like Merge Sort, that has a recurrence relationship given by,



We found that, the solution to this recurrence is theta ( n lg n). In this session, I am gonna teach you a few methods to solve in general any given recurrence relationship.

Tim : Professor, I would like to know what are the methods to solve a recurrence relationship ?

Professor : Of course ! They are

• Substitution Method
  
• Recursion Tree Method
• Master Method

Friends, there's no general method to solve a recurrence relationship. There are a few techniques that work some of the times. If you are lucky, yours will work for you.

So, class let's begin with the Substitution Method.

Substitution Method -
Substitution method has the following steps
1. Guess the solution - So, you say, "Oh! the running timer must be roughly bounded by n^2.
2. Verify if the recurrence satisifes the bounds using induction. Yeah, Substitution method uses Mathematical Induction.
3. From here we usually get the constant c and n0 for free.

Ed : Professor, could you illustrate to us, how to apply this method. I read this recurrence the other day ....



Professor : Okay, so let's solve your example Ed.
Let's guess the solution. You might wonder, what a stupid method! Asks you to guess the solution right at the beginning... But, lemme tell the solution you guess, this method can correctly tell how good your guess is.. whether your solution is right, wrong, or you are nearing the solution...

Well, what function multiplies the number by 4, if the argument is doubled ? If you think it must be . So, prima facie our guess is, it is bounded by O().



But, let's be a little liberal and check out if T(n) is bounded by . So, we'll first see how its done the easy way, and then we'll try to get the right answer by a considering a tighter bound.



So, we've proved the bounds. We shall now prove the tighter bound .

Lee : Professor, shall we proceed in the same way, we did as above ?

Professor : Yes, that's right! Let us solve it together.



Well, this may happen sometimes. You see, you may guess the asymptotic bound correctly, but, somehow your math doesn't verify it in induction. And this happens, because inductive assumption is not strong enough. So, when you encounter such a problem, give it a shot by subtracting certain lower order terms.