Big-O Notation — Mathematics Knowledge System

Overview

Big-O notation describes how an algorithm's running time or memory use grows as its input size grows, ignoring constant factors and lower-order terms. It answers 'how does this scale?' rather than 'how many seconds does this take on my laptop' — the question that actually matters for comparing algorithms as problems get large. It is the single most-used piece of mathematics in a computer science curriculum, appearing the moment students start analyzing algorithms.

Intuition

Imagine two algorithms sorting a list: one takes roughly n² steps, the other roughly n·log(n) steps, where n is the list length. For a list of 10 items the difference barely matters. For a list of 10 million items, n² is millions of times slower. Big-O captures exactly this: not the exact step count (which depends on hardware, implementation details, constant overhead) but the SHAPE of how work grows as n grows without bound.

Interactive Graph

Formal Definition

Definition

f(n) is O(g(n)) if f is eventually bounded above by a constant multiple of g:

f(n) = O(g(n)) \iff \exists\, c > 0, n_0 \text{ such that } f(n) \leq c\,g(n) \ \forall n \geq n_0

Definition

f(n) = \Omega(g(n)) \iff \exists\, c > 0, n_0 \text{ such that } f(n) \geq c\,g(n) \ \forall n \geq n_0

Big-Omega: an asymptotic lower bound

f(n) = \Theta(g(n)) \iff f(n) = O(g(n)) \text{ and } f(n) = \Omega(g(n))

Big-Theta: a tight bound (both upper and lower)

Notation

Notation	Meaning
$O(g(n))$	Asymptotic upper bound — grows no faster than g(n)
$\Omega(g(n))$	Asymptotic lower bound — grows at least as fast as g(n)
$\Theta(g(n))$	Tight bound — grows at the same rate as g(n)

Properties

Common complexity classes, from fastest to slowest growing

O(1) \subset O(\log n) \subset O(n) \subset O(n\log n) \subset O(n^2) \subset O(2^n) \subset O(n!)

Constants don't matter

O(cn) = O(n) \text{ for any constant } c > 0

Only the dominant term matters

O(n^2 + n) = O(n^2)

Sum rule (sequential steps)

O(f(n)) + O(g(n)) = O(\max(f(n), g(n)))

Product rule (nested loops)

O(f(n)) \cdot O(g(n)) = O(f(n) \cdot g(n))

Applications

Comparing algorithms (e.g. quicksort's average O(n log n) vs bubble sort's O(n²)) to choose the right one for large-scale data.

Worked Examples

n iterations, each O(1) work.
$T(n) = n \cdot O(1) = O(n)$

Answer: O(n)

Practice Problems

Difficulty 3/10

Binary search on a sorted list of n elements halves the search space each step. What's its time complexity?

Difficulty 5/10

An O(n²) report generator takes 2 seconds on 1,000 records. Roughly how long will it take on 10,000 records? On 100,000?

Difficulty 4/10

A function loops over every pair of users in a list of n users to check for mutual friendship. What is its time complexity, and why does it matter for a social network with millions of users?

Common Mistakes

Common Mistake

Treating Big-O as an exact measure of running time.

Big-O describes asymptotic GROWTH RATE, not actual seconds. An O(n) algorithm with huge constants can be slower than an O(n log n) one for realistic input sizes.

Common Mistake

Confusing Big-O (upper bound) with Big-Θ (tight bound).

Saying an algorithm is 'O(n²)' is technically true even if it's actually O(n) — O is only an upper bound. Θ is the precise statement most people mean informally.

Quiz

Which grows fastest as n → ∞?

O(n log n)O(n²)O(2ⁿ)O(log n)

Flashcards

1 / 2

Historical Background

The O(·) notation originates in analytic number theory — Paul Bachmann introduced it in 1894 and Edmund Landau popularized it, both studying the growth rate of number-theoretic functions. Donald Knuth imported and formalized the notation for computer science in the early 1970s, in his work analyzing algorithms, giving it the central role it has today in every algorithms course.

1894
Paul Bachmann introduces the O(·) notation in number theory
Paul Bachmann
1909
Edmund Landau popularizes and extends the notation
Edmund Landau
1976
Donald Knuth formalizes Big-O (and introduces Big-Ω, Big-Θ) for algorithm analysis
Donald Knuth

Summary

Big-O describes how running time/memory scales with input size, ignoring constants.
f(n)=O(g(n)) means f is eventually bounded above by c·g(n).
Common classes ordered by growth: O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ).
Sequential steps ADD complexities; nested loops MULTIPLY them.
Big-O is an upper bound; Big-Θ is the tight (exact growth rate) bound.

References

WebsiteWikipedia — Big O notation