ConceptSystems & CS
Big O notation
A mathematical notation used to describe an upper bound on the growth of a function.
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.
Asymptotic analysis3Function3Limit3Asymptotic growth2Inequalities2Algorithm analysis1Algorithm efficiency1Graph plotting1
Opens up
Concepts that name this one as a prerequisite.
Lecturers
6Each in their own terms, from the easiest level.
David J. Malan
A mathematical representation of an upper bound on the number of steps an algorithm takes as a function of the input size.Tom Leighton
A mathematical notation used to describe the limiting behavior of a function, ignoring constant factors and lower-order terms.Steven Strogatz
A mathematical notation used to describe the order of magnitude of terms being neglected.Michael Sipser
A notation used to describe the upper bound of a function's growth rate, ignoring constant factors.Ryan O'Donnell
A mathematical notation that describes the limiting behavior of a function, used to bound a function from above by another simpler function up to a constant factor.
Lectures that assume it
34The first 12 are shown.
- Harmonic Numbers Asymptotics
- Course Overview, Interval Scheduling
- Uninformed Search
- Asymptotics Tricks
- Divide and Conquer Recurrences
- The Word RAM Model
- Procedures and Processes: The Substitution Model, Recursion & Iteration
- Complexity: Fixed-Parameter Algorithms
- Dynamic Programming III: Parenthesization, Edit Distance, Knapsack
- Caching and Cache-Efficient Algorithms
- Dijkstra's Shortest Path Algorithm: Graph Theory and Optimization
- Amortization: Amortized Analysis
Connections
50The lectures that define it or assume it, and the concepts next to it.
Concepts9
Show 3 moreShow fewer
Lectures41
- Sums and Asymptotics
- MAE5790-2 One dimensional Systems
- Algorithms
- Data Structures
- Big Oh and Theta Notation for Algorithmic Efficiency
- Big O and friends
Show 35 moreShow fewer
- Time Complexity
- Harmonic Numbers Asymptotics
- Course Overview, Interval Scheduling
- Uninformed Search
- Asymptotics Tricks
- Divide and Conquer Recurrences
- The Word RAM Model
- Procedures and Processes: The Substitution Model, Recursion & Iteration
- Complexity: Fixed-Parameter Algorithms
- Dynamic Programming III: Parenthesization, Edit Distance, Knapsack
- Caching and Cache-Efficient Algorithms
- Dijkstra's Shortest Path Algorithm: Graph Theory and Optimization
- Amortization: Amortized Analysis
- Table Doubling, Karp-Rabin
- Dynamic Programming: Advanced DP
- PSPACE-Completeness
- Simulations and Turing Machine Variants
- Space Complexity
- Augmentation: Range Trees
- The Generalized Discrete Log Problem and the Security of Diffie-Hellman
- Time Complexity and Universal Turing Machines
- Hierarchy Theorems (Time, Space, and Nondeterministic)
- Hierarchy Theorems
- Succinct Structures I
- Time Hierarchy Theorem
- Course Introduction and Overview
- Savitch's Theorem and NL
- Computational Complexity
- Problems in P
- Quantum Computing for Computer Scientists
- Finding L-Functions out of Nothing
- Complexity Classes Examples
- Cybersecurity
- Quasilinear Cook–Levin Theorem
- Quantum Algorithms Synthesis III: Efficient Factoring & BQP