ConceptTheory & Algos
Asymptotic notation
Notation used to describe how a function grows in the limit.
Know first
Named as a prerequisite by the lectures that define this. The number is how many say so. A grey one has no page yet.
Opens up
Concepts that name this one as a prerequisite.
Lecturers
3Each in their own terms, from the easiest level.
Ryan O'Donnell
Two functions are asymptotic if their ratio tends to 1 as the input goes to infinity.Victor Costan
Notation used to describe the limiting behavior of a function, often making complex running time formulas look simpler.
Lectures that assume it
49The first 12 are shown.
- Priority Queues, Binary Heaps & O(n) Build-Max-Heap
- Insertion Sort, Binary Insertion & Merge Sort Recurrences
- Decision-Tree Ω(n log n) Lower Bound, Counting Sort & Radix Sort
- Divide & Conquer: FFT
- Divide and Conquer Recurrences
- The Word RAM Model
- Randomized Complexity: RP, coRP, and ZPP
- Sorting Algorithms
- Caching and Cache-Efficient Algorithms
- Data Compression and Shannon’s Noiseless Coding Theorem
- Amortization: Amortized Analysis
- Races and Parallelism
Connections
60The lectures that define it or assume it, and the concepts next to it.
Concepts8
Show 2 moreShow fewer
Lectures52
- Harmonic Numbers Asymptotics
- Sums and Asymptotics
- Asymptotic Complexity and Peak Finding (MIT 6.006, Recitation 1)
- Priority Queues, Binary Heaps & O(n) Build-Max-Heap
- Insertion Sort, Binary Insertion & Merge Sort Recurrences
- Decision-Tree Ω(n log n) Lower Bound, Counting Sort & Radix Sort
Show 46 moreShow fewer
- Divide & Conquer: FFT
- Divide and Conquer Recurrences
- The Word RAM Model
- Randomized Complexity: RP, coRP, and ZPP
- Sorting Algorithms
- Caching and Cache-Efficient Algorithms
- Data Compression and Shannon’s Noiseless Coding Theorem
- Amortization: Amortized Analysis
- Races and Parallelism
- Birthday Paradox Asymptotics
- Depth-First Search (DFS), Topological Sort
- Independence
- Integer Models
- Cache-Oblivious Algorithms: Medians and Matrices
- Table Doubling, Karp-Rabin
- Integer Arithmetic, Karatsuba Multiplication
- Dynamic Programming I: Fibonacci, Shortest Paths
- Factorial Asymptotics, Stirling's Formula
- Binomial Coefficients Asymptotics
- Dictionaries
- Static Trees
- Algorithmic Thinking & Peak Finding in 1D and 2D
- Models of Computation, Random Access Machine & Document Distance
- AVL Trees, Tree Rotations & Guaranteed O(log n) Height
- Divide & Conquer: Convex Hull, Median Finding
- Algorithms
- Integer Lower Bounds
- History of Memory Models
- Complexity of Basic Arithmetic
- Primes and Prime Fields
- Divide & Conquer: Van Emde Boas Trees
- Randomization: Skip Lists
- Extremal Combinatorics Meets Algorithms and Data Structures
- Analysis of Multithreaded Algorithms
- Random Variables
- Sorting in Linear Time
- Succinct Structures I
- Course Introduction and Overview
- Boolean Satisfiability (SAT)
- Ladner's Theorem and Mahaney's Theorem
- Recursion Trees and Binary Search Trees (MIT 6.006 Recitation 5)
- A Nearly Quadratic Lower Bound for Linear Optimization over Convex Bodies
- Problems in P
- Succinct Structures II
- Complexity Classes Examples
- Quasilinear Cook–Levin Theorem