When you write an algorithm, the most important question is: how does it behave as the input grows?
An algorithm that works fine for 100 items might take hours for 1 million items — or it might be just as fast.
Complexity analysis gives us mathematical tools to answer this question before running the code.
O(1)
→
O(log n)
→
O(n)
→
O(n log n)
→
O(n²)
→
O(2ⁿ)
← Slower as n grows
Why It Matters
What is Time Complexity?
Time complexity measures how the number of operations an algorithm performs grows with input size. We do not measure actual seconds — that depends on the computer and language. Instead, we count basic operations (comparisons, assignments) and express that count as a function of input size n.
The key idea is that we care about the rate of growth, not the exact count. An algorithm taking 3n + 7 operations and one taking 5n + 100 both grow at the same rate — linearly. For large n, the constants become irrelevant. We drop them and write simply O(n).
Real-world example: Binary Search finds a value in 1,000,000 sorted items in just 20 comparisons. Linear Search may need up to 1,000,000. Same task — 50,000× difference in effort. Complexity analysis predicts this gap without running either algorithm.
The Three Notations
Big-O · Big-Ω · Big-Θ
These three symbols describe different aspects of an algorithm's growth. Think of them as answers to three different questions about how your algorithm behaves in different situations.
Symbol
Name
Meaning
Answers the question
Example
O( )
Big-O
Upper bound — takes at most this long
What is the worst it can do?
Linear Search is O(n)
Ω( )
Big-Omega
Lower bound — takes at least this long
What is the best it can do?
Linear Search is Ω(1)
Θ( )
Big-Theta
Tight bound — upper and lower match
What is the exact growth rate?
Merge Sort is Θ(n log n)
Formal Definitions
f(n) = O(g(n)) iff ∃ c > 0, n₀ ≥ 1 such that f(n) ≤ c·g(n) for all n ≥ n₀
f(n) = Ω(g(n)) iff ∃ c > 0, n₀ ≥ 1 such that f(n) ≥ c·g(n) for all n ≥ n₀
f(n) = Θ(g(n)) iff f(n) = O(g(n)) AND f(n) = Ω(g(n))
The constants c and n₀ only need to exist — you do not need to find the smallest possible values. Any valid (c, n₀) pair is a correct proof. This is why Big-O proofs are non-unique.
Common mistake: Students think O(n²) means "exactly n² operations." It means "grows no faster than n²." An algorithm doing 3n² + 5n + 2 operations is still O(n²) — the lower terms vanish for large n.
How to Compute It
Counting Operations Step by Step
To find complexity, count how many times each line executes as a function of n, add them into T(n), then drop constants and lower-order terms. Three valid approaches exist — they always produce the same final O( ) result.
🟠
Statement Execution Count
Count every executable line — assignments, conditions, returns. Gives the largest raw number but the same final O( ).
Most detailed
🔵
Comparison Count
Count only conditional checks — loop conditions and if-statements. Standard in sorting and searching analysis.
Most common
🟣
Dominant Operation
Identify the single operation representing core work. All others are proportional to it. Cleanest for proofs.
Cleanest
🟢
Why They All Agree
Three counts give three different T(n) expressions — but all simplify to the same Big-O class. Constants always vanish.
Key insight
Worked Example — Linear Search
O(n)
function linearSearch(arr, n, target):
for i = 0 to n-1: // executes n+1 times (loop condition)if arr[i] == target: // executes n times (worst case)return i // executes 0 or 1 timesreturn -1// executes 1 time
Counting statements: T(n) = 1 + (n+1) + n + 1 = 2n + 3 Drop constants & coefficient: 2n + 3 → 2n → n Result: O(n)
Best case (found at index 0): 1 comparison → Ω(1) |
Worst case (not found): n comparisons → O(n) |
Average: n/2 comparisons → Θ(n)
Worked Example — Nested Loops (Matrix Sum)
O(n²)
function matrixSum(arr, n):
total = 0// 1 timefor i = 0 to n-1: // n+1 times (outer loop condition)for j = 0 to n-1: // n(n+1) times (inner loop condition)
total = total + arr[i][j] // n² times ← dominant operation ⭐return total // 1 time
T(n) = 1 + (n+1) + n(n+1) + n² + 1 = 2n² + 2n + 3 Drop lower-order term (2n) and constants (3): → 2n² → n² Result: O(n²) — every additional nested loop multiplies complexity by n.
Two golden rules for simplification:
1. Drop additive constants — O(n + 100) = O(n)
2. Drop multiplicative constants — O(3n²) = O(n²)
Only the fastest-growing term survives. Big-O cares about the shape of growth, not the exact count.
Three Cases
Best, Worst, and Average Case
The same algorithm can behave very differently depending on the input it receives. We analyse three cases to get a complete picture of an algorithm's performance.
Best Case — Ω
Most Favourable Input
The algorithm finishes as quickly as possible. For Linear Search: target is at index 0 — only 1 comparison needed.
Described with Ω (Omega) — lower bound on running time.
Worst Case — O
Least Favourable Input
The algorithm does maximum work. For Linear Search: target absent — all n elements checked.
Described with O (Big-O) — upper bound. This is the most commonly reported case.
Average Case — Θ
Expected Performance
Expected performance across all possible inputs assuming uniform distribution. For Linear Search: n/2 comparisons on average.
Described with Θ (Theta) when upper and lower bounds match.
Why worst case is reported most often: In critical systems (databases, operating systems, real-time software), you need a guarantee that performance will never exceed a certain bound. Best and average cases can be misleading — the worst case is the safety guarantee.
Reference
Common Complexity Classes
Notation
Name
Example Algorithm
n=10
n=100
n=1,000
O(1)
Constant
Array access by index
1
1
1
O(log n)
Logarithmic
Binary Search
3
7
10
O(n)
Linear
Linear Search
10
100
1,000
O(n log n)
Linearithmic
Merge Sort, Heap Sort
33
664
9,966
O(n²)
Quadratic
Bubble Sort, Selection Sort
100
10,000
1,000,000
O(2ⁿ)
Exponential
Recursive Fibonacci (naïve)
1,024
10³⁰
💀
The exponential cliff: At n=100, an O(2ⁿ) algorithm needs more operations than there are atoms in the observable universe. This is why exponential algorithms are considered computationally intractable for large inputs — no computer upgrade will save you.
Interactive Learning
Practice With These Games
Work through the games below in order — Big-O Arena for intuition, Complexity Counter for hands-on counting, Limit Analyser for the formal definitions, and Prove It Quiz to test yourself.