ConceptTheory & Algos
Amortized analysis
An analysis technique where we bound the total cost of a sequence of operations rather than the individual running time of each operation.
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.
Indirection3Ordered file maintenance2Potential method22-3 Tree insertion amortized analysis1Access lemma1Accounting method1Aggregate method1Amortized analysis of rebalance cost1Amortized analysis with potential method1Amortized cost in (2,5)-trees1Amortized cost of splitting1Amortized tree construction analysis1
Lecturers
3Each in their own terms, from the easiest level.
Erik Demaine
A method to bound the average cost of an operation over a sequence of operations.Ryan O'Donnell
An analysis method where you bunch up steps rather than timing every single step individually.
Lectures that assume it
13The first 12 are shown.
- Geometric Structures I
- Integer Models
- Static Trees
- Cache-Oblivious Structures I
- Dijkstra's Algorithm: Greedy Single-Source Shortest Paths
- Dynamic Connectivity Lower Bound
- Cache-Oblivious Algorithms: Searching & Sorting
- Persistent Data Structures
- Dynamic Graphs II
- Extremal Combinatorics Meets Algorithms and Data Structures
- Memory Hierarchy Models
- Sorting in Linear Time
Connections
22The lectures that define it or assume it, and the concepts next to it.
Concepts6
Lectures16
- Amortization: Amortized Analysis
- Dynamic Graphs I
- Hierarchy Theorems (Time, Space, and Nondeterministic)
- Geometric Structures I
- Integer Models
- Static Trees
Show 10 moreShow fewer
- Cache-Oblivious Structures I
- Dijkstra's Algorithm: Greedy Single-Source Shortest Paths
- Dynamic Connectivity Lower Bound
- Cache-Oblivious Algorithms: Searching & Sorting
- Persistent Data Structures
- Dynamic Graphs II
- Extremal Combinatorics Meets Algorithms and Data Structures
- Memory Hierarchy Models
- Sorting in Linear Time
- Dynamic Optimality I