Opening Asymptotic Complexity and Peak Finding (MIT 6.006, Recitation 1)
Asymptotic Complexity and Peak Finding (MIT 6.006, Recitation 1)
- Length
- 54 min
- Level
- Undergraduate
- Recorded
- MIT2013
Chapter 1 of 5: Before the lecture
Bounds factorials with Stirling-type estimates, then halves a matrix on column maximums to find a peak in .
Asymptotic complexity analysis describes how a function grows for very large inputs, keeping the dominant term and dropping constant factors. In this MIT 6.006 recitation, Costan reduces a polynomial to and reviews the formal definitions of Big-O, Omega and Theta. Exercises cover logarithm rules, showing why bases and exponents inside a logarithm become constant factors, and bound factorials with Stirling-type approximations. The second half turns to peak finding: a binary search gives for the one-dimensional case. Recursing on column maximums extends the method to matrices, and solving that recurrence yields . The session assumes basic algebra, logarithms and the recurrences from the first lecture.
Asymptotic complexity analysis describes how a function grows for very large inputs, keeping the dominant term and dropping constant factors. In this MIT 6.006 recitation, Costan reduces a polynomial to and reviews the formal definitions of Big-O, Omega and Theta. Exercises cover logarithm rules, showing why bases and exponents inside a logarithm become constant factors, and bound factorials with Stirling-type approximations. The second half turns to peak finding: a binary search gives for the one-dimensional case. Recursing on column maximums extends the method to matrices, and solving that recurrence yields . The session assumes basic algebra, logarithms and the recurrences from the first lecture.

This lecture
Lecture 25 of 31 of Introduction to Algorithms.
Choose a node to see how it connects to this lecture. What comes before is on the leftat the top. What comes after is on the rightat the bottom. The ring is what it teaches. People and places are above. Other lectures and books are below.
Press a chosen node again to open it.
Your comment is kept while you sign up.Sign in