Skip to main content
AmigoFish

Recurrence Equations and Asymptotic Notation

From Connected Components of Chaos · · 19 min

This plays from the publisher's own server. We do not host a copy.

Open at the source

Not rated yet

Description

This episodes presents methods for solving recurrence equations, which are crucial for analyzing the time complexity of recursive algorithms. It introduces asymptotic notations (Big O, Big Omega, Big Theta, little o, little omega) to describe the growth of functions. The lecture then explores several techniques for solving recurrences, including the substitution method, iteration method (and recursion trees), the Master Theorem, and solving homogeneous and non-homogeneous linear recurrences. Specific examples such as merge sort, binary search, and the Towers of Hanoi are used to illustrate these techniques. Finally, the limitations of the Master Theorem are discussed, along with strategies for handling cases where it is not applicable.

Visit our website here:https://sites.google.com/view/connected-components/home

Back to Connected Components of Chaos · Report a problem