Complexity Olympics

Four events. Four different growth rates. Which scales?

Year 9 Computer Science — Algorithmic Complexity

The Big Question

A sorting algorithm works correctly on 10 items.

How does it perform on 10,000 items? On 10 million?

The answer depends on the algorithm's growth rate — how the number of steps grows as the input grows.

That's what Big-O notation measures.

The Four Events

Station 1: O(1)

Direct lookup — always 1 step

Station 2: O(log n)

Binary search — grows very slowly

Station 3: O(n)

Find maximum — proportional to n

Station 4: O(n²)

All pairs — grows as n squared

Station Instructions

Read the station card carefully
Do the activity for small, medium, and large n
Record results on your worksheet
Note the pattern — how does work grow as n increases?

You have ~7 minutes at each station. When teacher signals: rotate.

Plot Your Results

Add all four complexity classes to the graph on your worksheet.

Use different symbols so you can tell them apart.

Notice:

O(1) = flat horizontal line
O(log n) = gentle curve, nearly flat
O(n) = straight diagonal line
O(n²) = steep curve, shoots upward

The Scale Problem

For n=10:

O(1):   1 step
O(log n): 3 steps
O(n):   10 steps
O(n²):  45 steps

Seems manageable. But for n=1,000,000:

O(1):    1 step
O(log n): 20 steps
O(n):    1,000,000 steps
O(n²):   ~500,000,000,000 steps

Real Engineering Decisions

A social network has 1 billion users.

O(n) search: 1 billion comparisons per lookup. At 1GHz: ~1 second each. Unacceptable.

O(log n) with indexed database: ~30 comparisons per lookup. Instant.

This is why database indexes exist. This is why algorithm choice matters.

Key Takeaway

The growth rate of an algorithm matters as much as its correctness.

O(n²) becomes impractical at scale.
O(log n) scales magnificently.

Choosing the right complexity class is a core engineering decision.

Discussion

At what size n does O(n²) become slower than O(n log n)?
If you were building a search engine for 100 billion web pages, what complexity class would you need?
Can you always improve an O(n²) algorithm to O(n)? Or is there sometimes no choice?