Recurrence Relations: Substitution Method for Asymptotic Analysis

Using the Substitution Method (guess and inductively prove) to prove asymptotic bounds hold for recurrences. Table of Contents: 00:00 - Introduction and Prerequisites 00:37 - Linked List Search 01:33 - Simplifications 03:17 - Mergesort Upper Bound 03:48 - Guess Too Big 04:39 - Guess Too Small 04:52 - Lower Bound Proof 05:21 - Tight Lower Bound 05:34 - Failed Proof 06:25 - Lower Order Terms 07:41 - Weirder Recurrences 08:11 - What's Next?