- Count the operations of a code fragment and find its growth class
- Apply the formal definitions of O, Ω and Θ
- Estimate the running time of a recursive algorithm with the master theorem
Leyla wrote a search feature for an online library: with 1,000 books it answers instantly. A year later the catalogue holds 10 million books and the same feature “thinks” for minutes. The computer did not get slower — the algorithm's running time simply grows very fast with the size of the data. In this lesson we learn to measure that growth and predict it in advance.
Counting operations
Seconds depend on the machine, the language and background processes, so we judge an algorithm not in seconds but by the number of basic operations: comparisons, assignments, arithmetic, array accesses. This count is a function of the input size n and is usually taken for the worst case — the guarantee we can give the user.
A function has an outer loop over i = 0 … n − 1 and an inner loop over j = i + 1 … n − 1; the inner body does one multiplication (a[i] * a[j]). How many times does the body run, and what growth class is that?
Show solutionHide solution
Sum: (n − 1) + (n − 2) + … + 1 + 0 = n(n − 1)/2.
For n = 1000 that is 499,500 multiplications.
n(n − 1)/2 = 0.5n² − 0.5n; drop the lower-order term and the constant → Θ(n²), a quadratic algorithm.
- ninput size (number of elements)
Gauss's sum: the operation count of “each element with every other once” nested loops.
Asymptotic notation: O, Ω, Θ
Writing f(n) = O(g(n)) means that for large enough n the function f(n) is bounded above by a constant multiple of g(n): f grows no faster than g. Ω gives a lower bound, and Θ gives both at once — the exact rate of growth.
- f(n)the algorithm's operation count
- g(n)the comparison function (n, n², n log n …)
- ca positive constant
- n₀the size from which the inequality holds
Ω is a lower bound; Θ is both an upper and a lower bound (“sandwiched” between two constants).
Given f(n) = 3n² + 5n + 2, prove that f(n) = Θ(n²) by giving the constants c and n₀.
Show solutionHide solution
3n² + 5n + 2 ≤ 3n² + 5n² + 2n² = 10n² → c = 10, n₀ = 1, hence f = O(n²).
Lower bound: for n ≥ 1, 5n + 2 > 0, so 3n² + 5n + 2 ≥ 3n² → c = 3, hence f = Ω(n²).
Together: 3n² ≤ f(n) ≤ 10n² → f(n) = Θ(n²).
Common complexity classes
| Class | Name | Typical algorithm | n = 10 | n = 1000 |
|---|---|---|---|---|
| O(1) | constant | array access by index | 1 | 1 |
| O(log n) | logarithmic | binary search | ≈ 3 | ≈ 10 |
| O(n) | linear | linear search, finding the maximum | 10 | 10³ |
| O(n log n) | linearithmic | merge sort | ≈ 33 | ≈ 10⁴ |
| O(n²) | quadratic | bubble sort, checking all pairs | 100 | 10⁶ |
| O(2ⁿ) | exponential | trying all subsets | 1024 | ≈ 10³⁰¹ |
| O(n!) | factorial | trying all permutations | 3,628,800 | ≈ 10²⁵⁶⁷ |
def binary_steps(n):
steps, lo, hi = 0, 0, n - 1
while lo <= hi:
mid = (lo + hi) // 2
steps += 1
lo = mid + 1
return steps
def pair_steps(n):
count = 0
for i in range(n):
for j in range(i + 1, n):
count += 1
return count
print('n', 'log', 'linear', 'pairs')
for n in [10, 100, 1000, 2000]:
print(n, binary_steps(n), n, pair_steps(n))▸ Expected output
n log linear pairs 10 4 10 45 100 7 100 4950 1000 10 1000 499500 2000 11 2000 1999000
| Complexity | largest n handled in ≈ 1 second |
|---|---|
| O(n) | ≈ 10⁸ |
| O(n log n) | ≈ 5 · 10⁶ |
| O(n²) | ≈ 10⁴ |
| O(n³) | ≈ 450 |
| O(2ⁿ) | ≈ 26 |
| O(n!) | ≈ 11 |
Recurrences and the master theorem
The running time of a recursive algorithm is itself written recursively. Binary search continues in one half: T(n) = T(n/2) + c. Merge sort splits the array into two halves, sorts each one and merges them in linear time: T(n) = 2T(n/2) + cn. Such an equation is called a recurrence.
- T(n)running time on an input of n elements
- 2T(n/2)2T(n/2)recursive work on the two halves
- cnsplitting and merging work (linear)
Recursion tree: level k has 2ᵏ subproblems of size n/2ᵏ, so the level's total work is 2ᵏ · c · n/2ᵏ = cn. There are log₂ n levels, so the total is cn · log₂ n.
- anumber of recursive calls (a ≥ 1)
- bfactor by which the size shrinks (b > 1)
- dexponent of the splitting and combining work (d ≥ 0)
Master theorem (simplified form): compare a with bᵈ. a < bᵈ → Θ(nᵈ); a = bᵈ → Θ(nᵈ · log n); a > bᵈ → Θ(nᵖ), where p = log a / log b.
The intuition: the ratio a/bᵈ tells how the work changes from one level of the recursion tree to the next. When a < bᵈ the work shrinks going down and the root's nᵈ dominates; when a = bᵈ all log n levels do equal work; when a > bᵈ the work grows and the leaves (there are nᵖ of them) decide.
Solve:
a) T(n) = 2T(n/2) + n
b) T(n) = T(n/2) + 1
c) T(n) = 8T(n/2) + n²
d) T(n) = 2T(n/2) + n²
Show solutionHide solution
b) a = 1, b = 2, d = 0: bᵈ = 1 = a → Θ(n⁰ · log n) = Θ(log n) (binary search).
c) a = 8, b = 2, d = 2: bᵈ = 4 < 8 → Θ(nᵖ), p = log₂ 8 = 3 → Θ(n³) (naive recursive matrix multiplication).
d) a = 2, b = 2, d = 2: bᵈ = 4 > 2 → Θ(n²) — the work at the root dominates.
import math
def T(n):
if n == 1:
return 1
return 2 * T(n // 2) + n
for k in [2, 4, 8, 16, 20]:
n = 2 ** k
print(n, T(n), n * k + n, round(T(n) / (n * math.log2(n)), 3))▸ Expected output
4 12 12 1.5 16 80 80 1.25 256 2304 2304 1.125 65536 1114112 1114112 1.062 1048576 22020096 22020096 1.05
Key points
- Algorithms are judged by the number of basic operations as a function of n, usually in the worst case — not in seconds.
- O is an upper bound, Ω a lower bound, Θ the exact growth rate; constants and smaller terms are dropped.
- The order of classes: 1 < log n < n < n log n < n² < 2ⁿ < n!.
- Sequential blocks add, nested loops multiply, halving gives log n.
- For T(n) = aT(n/b) + Θ(nᵈ) compare a with bᵈ; T(n) = 2T(n/2) + n → Θ(n log n).
Check yourself
10 questions. Every correct answer earns XP.