Solving Recurrences

This lecture covers the analysis of sorting algorithms like Insertion Sort and Merge Sort, emphasizing in-place rearrangement of numbers within arrays. It also delves into the analysis of divide-and-conquer algorithms, specifically focusing on Merge Sort. The lecture then progresses to solving recurrences through induction, discussing upper and lower bounds with proofs. Additionally, it addresses the complexities introduced by floors and ceilings in recurrence relations and common mistakes in using the substitution method. The Master method is introduced as a tool to solve recurrences of a specific form.