Complexity Analysis
Measure how running time and memory grow with input size. Big-O notation has its own page earlier in this subject.
This is an overview — pick a sub-topic below.
Sub-topics (8)
Time Complexity
Count how the number of basic steps grows with input size $n$.
Space Complexity
How much extra memory an algorithm needs as $n$ grows.
Big Omega
$\Omega(f(n))$ — an asymptotic lower bound: the algorithm takes at least this long (for large $n$).
Big Theta
$\Theta(f(n))$ — a tight bound: both $O(f)$ and $\Omega(f)$.
Amortized Analysis
The average cost per operation over a worst-case sequence of operations.
Best, Average and Worst Case
The same algorithm can behave differently on different inputs.
Recurrence Relations
Equations describing a recursive algorithm's cost.
Master Theorem
Solves recurrences of the form $T(n) = aT(n/b) + f(n)$.
Spotted a mistake or want to add detail? Suggest an improvement — Content Contributors' edits are reviewed by editors before they go live.
Discussion (0)
Sign in or join free to ask questions and discuss this topic.