Time and Space Complexity: Big O, Ω, and Θ
How to describe an algorithm's growth rate independent of any specific machine, why worst-case matters most, and the difference between measuring and reasoning about performance.
What you'll learn
- Determine the Big O time complexity of a piece of code by counting operations relative to input size
- Explain the difference between best, average, and worst case, and why worst case is usually the headline number
- Distinguish empirical timing from formal asymptotic analysis, and explain why neither alone proves a growth-rate claim
Prerequisites
Explanation
Big O notation describes how an algorithm's running time (or memory use) grows as the input size n grows, ignoring constant factors and lower-order terms — it answers "if I double the input, roughly how much more work happens?" rather than "how many milliseconds does this take on my laptop." O(1) (constant) means the work doesn't grow with n at all (accessing arr[0]). O(log n) (logarithmic) means the work barely grows as n grows — doubling n adds only one more step (binary search, covered later in this course). O(n) (linear) means work grows proportionally to n (a single loop over the input). O(n log n) is the complexity of the best comparison-based sorts (merge sort, covered later). O(n²) (quadratic) means work grows with the square of n — typically a loop nested inside another loop, each running roughly n times.
Big O specifically describes an upper bound on growth — technically, Big O is one member of a family: Big Ω (Omega) describes a lower bound (the algorithm takes at least this long), and Big Θ (Theta) describes a tight bound (both upper and lower — the algorithm's growth rate genuinely is this, not merely "at most" this). In casual practice, "Big O" is often used loosely to mean "the tight bound," but the distinction matters in precise contexts: an algorithm that's O(n²) in the worst case might be Θ(n) in a specific favorable case, and both statements can be true about the same algorithm without contradicting each other.
Best, average, and worst case describe how an algorithm's complexity varies across different inputs of the same size — a linear search's best case (the target is the first element) is O(1), but its worst case (the target is last, or absent) is O(n); the average case, over many random inputs, is also O(n) (roughly half the array, on average). Worst case is usually the headline number precisely because it's a guarantee — "this will never take longer than X for input size n" — which matters far more for a real system's reliability than a favorable average that could still, on an unlucky input, be slow. Amortized analysis describes the average cost per operation across a whole sequence of operations, even when individual operations vary wildly — an ArrayList's .add() is O(1) amortized even though any individual call that triggers a resize is genuinely O(n), because those expensive resizes happen rarely enough that their cost, spread proportionally across all the O(1) calls between them, averages out to O(1) per call.
Crucially, empirical timing is not the same thing as complexity analysis. Running two algorithms on a small input and timing which one finishes first tells you almost nothing reliable about their asymptotic growth rate — a technically-O(n²) algorithm can easily outrun a technically-O(n log n) one on small n, because Big O deliberately ignores constant factors that dominate at small sizes. Real complexity analysis comes from counting operations symbolically as a function of n and reasoning about how that function grows, not from a stopwatch — timing is useful for real-world performance work, but it's a different kind of evidence than an asymptotic growth-rate claim, and one browser-run test on a handful of inputs proves neither.
Example
Counting operations symbolically, not timing -- this is what actually establishes a complexity claim.
// O(n): one pass, work grows linearly with input size.
function sumArray(arr) {
let total = 0;
for (const x of arr) total += x; // runs exactly arr.length times
return total;
}
// O(n^2): a loop nested inside a loop, each running up to n times.
function hasDuplicatePair(arr) {
for (let i = 0; i < arr.length; i++) {
for (let j = i + 1; j < arr.length; j++) {
if (arr[i] === arr[j]) return true; // up to ~n*(n-1)/2 comparisons
}
}
return false;
}
// The claim "sumArray scales better than hasDuplicatePair for large inputs" comes from
// counting these loop structures -- NOT from timing them on one specific array size.Try it yourself
Count the operations in this function by hand before running -- is it O(n) or O(n^2)?
Code editor. Press Escape then Tab to leave the editor if keyboard focus becomes trapped. Press Control+Shift+M inside the editor to toggle Tab-key focus trapping.
Guided exercise
Guided exercise
Write classifyComplexity(codeShape) that returns the Big O class for a simplified description of a loop structure. Input is one of: 'single-loop', 'nested-loop', 'no-loop', 'halving-loop' (a loop that divides its range by 2 each iteration, like binary search). Return exactly: 'O(1)', 'O(n)', 'O(n^2)', or 'O(log n)' respectively.
Checks: no-loop maps to O(1) · single-loop maps to O(n) · nested-loop maps to O(n^2) · halving-loop maps to O(log n)
Code editor. Press Escape then Tab to leave the editor if keyboard focus becomes trapped. Press Control+Shift+M inside the editor to toggle Tab-key focus trapping.
Stuck? Get a hint.
Independent exercise
Independent exercise
Write worstCaseLinearSearchSteps(n) returning the worst-case number of comparisons a linear search over n elements requires (n, since the target might be last or absent), and bestCaseLinearSearchSteps(n) returning the best case (1, if n > 0; 0 if n === 0, since there's nothing to search).
Checks: worst case scales linearly with n · worst case for an empty input is 0 · best case is a constant 1 step for non-empty input · best case for an empty input is 0, not 1
Code editor. Press Escape then Tab to leave the editor if keyboard focus becomes trapped. Press Control+Shift+M inside the editor to toggle Tab-key focus trapping.
Stuck? Get a hint.
Common mistakes
- Timing two algorithms on a small input in a browser console and concluding one 'is' faster asymptotically -- constant factors dominate at small n, so this proves nothing about growth rate at scale.
- Reporting only the average case and ignoring worst case for something used in a reliability-sensitive path -- an average that's fine but a worst case that's catastrophic is a real, common source of production incidents.
- Treating O(n) and O(n) + O(n) as different complexity classes -- Big O drops constant factors and lower-order terms; O(2n) and O(n) describe the same growth rate.
Knowledge check
Takeaway
Big O describes how work grows with input size, not how fast something runs on a specific machine or input — establish it by counting operations symbolically, and prefer worst-case guarantees over average-case optimism for anything reliability-sensitive.
Summary
O(1), O(log n), O(n), O(n log n), and O(n^2) are the growth-rate classes you'll see constantly. Big Θ is a tight bound; Big Ω is a lower bound; Big O is technically an upper bound, though it's often used loosely for the tight bound. Amortized analysis averages cost across a sequence of operations. Empirical timing and asymptotic analysis are different kinds of evidence.
References
Your notes
Notes save automatically.
Finished this lesson?
Mark it complete to track your progress and schedule a future review.
AI tutor
The optional AI tutor isn't enabled in this deployment. All lessons, exercises, quizzes, and search work fully without it.