Recurrence Relations: Recursion Tree Method

To solve recurrence relations, expanding the recursion tree can be used to either get an educated guess to use with the substitution method, or to directly prove a solution using induction.

Table of Contents:

00:00 - Introduction and Prerequisites
00:13 - Linear Search Example: T(n) = T(n-1) + 1
01:50 - Substitution Required?
02:31 - Inductive Proof (Skipping Substitution)
03:16 - MergeSort Example: T(n) = 2T(n/2) + n
04:35 - Why Substitution
05:26 - What's Next

[TheBlackMastadonte]

you're about to help me ace this Algorithms midterm. Thanks sir

[azjkjensen]

I was only moderately engaged until the "Jack, get down from there!" comment.

[Andrey-nydv]

4:55 I understand how you get line with i's. I am wondering if you are simply substituting i for lg(n) just because it is true for all positive i's, and this way you get that it is O(lgn)
Also, just some feedback. 2:45 It would help if you had question marks above the statements that need to be proven because if you don't have them, I have an impression that we know it already. It is even more confusing when you start proving the "proven" statement on the next line. Hope that helps

[rashmiprabhakar]

At 4.38, how do you deduce 2^lgn T(n/2^lgn) + nlgn = nT(1) + nlgn ?

[haoyangliu]

if(your joke is getting dumber)
{
make more dumber jokes;
}
recursively.