ConceptTheory & Algos
Time complexity
The total time required for an algorithm to complete its execution in the worst case.
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
2Each in their own terms, from the easiest level.
Ryan O'Donnell
A function mapping natural numbers to natural numbers that gives the maximum number of steps a decider algorithm takes on any input of a given length.
Lectures that assume it
35The first 12 are shown.
- Procedures and Processes; Substitution Model (SICP Lecture 1b)
- Exponential Time Hypotheses: ETH and SETH
- Sorting Algorithms
- Harvard CS50’s Artificial Intelligence with Python – Full University Course
- Hardness within P
- P and NP, SAT, Poly-Time Reducibility
- NP-Completeness Reductions
- Time/Space Tradeoffs for SAT
- Space Complexity
- BPP (Bounded-Error Probabilistic Polynomial Time) Complexity Class
- Time Complexity and Universal Turing Machines
- Hierarchy Theorems (Time, Space, and Nondeterministic)
Connections
44The lectures that define it or assume it, and the concepts next to it.
Concepts7
- Message complexity
- Turing machine
- Time hierarchy theorem
- Exponential time hypothesis
- Space complexity
- Amortized cost
Show 1 moreShow fewer
Lectures37
- Simulations and Turing Machine Variants
- Asynchronous Distributed Algorithms: Shortest-Paths Spanning Trees
- Procedures and Processes; Substitution Model (SICP Lecture 1b)
- Exponential Time Hypotheses: ETH and SETH
- Sorting Algorithms
- Harvard CS50’s Artificial Intelligence with Python – Full University Course
Show 31 moreShow fewer
- Hardness within P
- P and NP, SAT, Poly-Time Reducibility
- NP-Completeness Reductions
- Time/Space Tradeoffs for SAT
- Space Complexity
- BPP (Bounded-Error Probabilistic Polynomial Time) Complexity Class
- Time Complexity and Universal Turing Machines
- Hierarchy Theorems (Time, Space, and Nondeterministic)
- Hopcroft–Paul–Valiant Theorem
- B+Tree Indexes
- Hierarchy Theorems
- Strange Gaps in the Local Time Hierarchy
- Time Hierarchy Theorem
- Course Introduction and Overview
- Ladner's Theorem and Mahaney's Theorem
- Savitch's Theorem and NL
- NL-Completeness and Logspace Reductions
- Impagliazzo T Wigderson, and Nisan's Pseudorandom Generators
- Why is P vs. NP Difficult?
- Hardness vs. Randomness II
- Computational Models: Turing Machines
- Space Complexity, PSPACE, Savitch's Theorem
- Provably Intractable Problems, Oracles
- Nondeterminism
- Time Complexity
- Multigrid Methods for Laplace's Equation
- A Fine-Grained Analogue of Schaefer's Theorem in P
- Oracles, and the Polynomial Time Hierarchy vs. circuits
- Beyond Worst-Case Analysis
- Complexity Classes Examples
- Quasilinear Cook–Levin Theorem