First exams 2027 · SL & HL

B2.4.1 · Programming algorithms

Big O notation: measuring how an algorithm scales

Two algorithms can both give the right answer. Big O notation is how you tell which one is going to fall over first once the input gets big.

Core for SL & HL Typically 3–6 marks · AO3 Command term: describe

Explainer

Ravensbourne High's photocopier prints one handout per student. Printing for a class of 30 takes about 30 times as long as printing for 1 student. Print for two full classes (60 students) and it takes about twice as long as one class. That relationship, the work growing in step with how much there is to do, is exactly what Big O time complexity captures.

Df

Big O notation describes how the number of steps an algorithm takes grows as the input size, usually written n, grows. It doesn't measure exact seconds, which change depending on the computer, it measures the shape of the growth.

2

Time complexity describes how the number of steps grows with input size. Space complexity describes how the amount of memory used grows with input size. Both are written using the same Big O notation, they just measure different things.

Explainer

Counting a piece of code's own steps

To find an algorithm's Big O, count how many times its slowest-growing line actually runs, for an input of size n, in the worst case.

1

One loop over n items runs n times: O(n).

for student in range(n): print_handout(student)
2

A loop inside another loop, both over n, runs n × n times: O(n²).

for student in range(n): for other_student in range(n): check_same_name(student, other_student)
3

No loop at all, one fixed number of steps regardless of n: O(1).

remaining = paper_stock - handouts_printed

Explainer

Dropping constants and lower-order terms

Real algorithms rarely count out to a clean n or n², they usually come out as a full expression, like 3n² + 40n + 12. Big O only keeps the part that matters once n gets large.

!

Keep only the fastest-growing term, and drop its multiplier. 3n² + 40n + 12 becomes O(n²). The 40n and the 12 shrink to nothing compared to n² once n is large, and the 3 doesn't change which term grows fastest, only how big the steps are.

Explainer

The common growth rates, slowest to fastest

NotationNameWhat it means
O(1)ConstantSame number of steps no matter how big n gets.
O(log n)LogarithmicSteps grow very slowly, each doubling of n only adds roughly one more step.
O(n)LinearSteps grow in direct proportion to n.
O(n²)QuadraticSteps grow with the square of n, common with one loop nested inside another.
O(2ⁿ)ExponentialSteps roughly double every time n increases by one, becomes unusable very quickly.

This is the order they're usually compared in, from best-scaling to worst-scaling, as n grows large.

Explainer

Space complexity: the same idea, applied to memory

Space complexity asks a different question about the same code: how much memory does it need, as n grows?

O(1) space 
total_printed = 0
for student in range(n):
    total_printed = total_printed + 1

total_printed is one variable, overwritten every pass. It takes the same memory whether n is 5 or 5000.

O(n) space 
printed_names = []
for student in range(n):
    printed_names.append(student)

printed_names grows by one entry every pass. Store all n students, and the memory used grows right along with n.

Explainer

Choosing an algorithm by scalability and efficiency

The "best" algorithm depends on what it's actually going to be used for, not on which one sounds cleverest.

•

Small, fixed inputs: if Ravensbourne's photocopier room only ever handles one class (about 30 students) at a time, an O(n²) approach is often perfectly fine, n never gets large enough for the difference to matter.

•

Large or growing inputs: if the same system had to handle the whole school (2000 students) printing at once, an O(n²) approach would slow down dramatically, an O(n) or O(n log n) approach scales far better.

•

Real-time requirements: a system that has to respond instantly, regardless of how much data it holds, needs O(1) or O(log n), not something that gets slower as more data piles up.

Worked example

Three photocopier jobs, three growth rates

The same three code shapes from the explainer, counted out for a real, small class of 4 students, to see the actual numbers before trusting the notation.

Counting real steps for n = 4 Step 1 of 3

Step 1. One loop, O(n). 4 students, one handout each: 4 steps.

n = 4 count = 0 for student in range(n): count = count + 1 print("Steps:", count)
Steps: 4

Step 2. Nested loop, O(n²). Every one of the 4 students compared against every other: 4 × 4 = 16 steps.

count = 0 for student in range(n): for other in range(n): count = count + 1 print("Steps:", count)
Steps: 16

Step 3. No loop, O(1). Exactly 1 step, whether n is 4 or 4000.

remaining = 500 - 4 print("Steps: 1")
Steps: 1

Try it yourself

Watch O(n²) growth for real

The same nested-loop counter run for n = 5, 10 and 20. Change the values in the list and press Run to see whether the counts still roughly match n × n.

main.py
Loading Python engine…
Output
Press Run to see the output here.

Running in offline fallback mode. The full Python engine couldn't load (blocked school network, or no internet), so this console switched automatically to a small hand-written engine. It supports this page's loops and functions, but it isn't full Python.

Worked example

Simplifying a real expression

An algorithm's real step count comes out as 3n² + 40n + 12. Substituting real numbers shows exactly why the smaller terms stop mattering.

n3n²40n+12Total
1030040012712
10030,0004,0001234,012
10,000300,000,000400,00012300,400,012

At n = 10, the 40n term (400) is actually bigger than the 3n² term (300). But by n = 10,000, 3n² is 300 million while 40n is only 400,000, barely a rounding error by comparison. The 3n² term is what decides how the total behaves once n is genuinely large, which is exactly why Big O keeps only that term: O(n²).

Check your understanding

An algorithm performs 5n² + 100n + 4 operations for an input of size n. What is its Big O time complexity?

Common mistake

A well-documented pattern in the syllabus's own worked simplification rule

RecurringAfter correctly counting an algorithm's operations, a common error is writing the full, unsimplified expression as the final Big O answer, or dropping the wrong term entirely, keeping a smaller term instead of the one that actually dominates.

✕

Wrong, not simplified: "The time complexity is O(5n² + 100n + 4)." Counted correctly, but never reduced to the one term that actually decides the growth.

✕

Wrong, dropped the wrong term: "The time complexity is O(100n), since 100 is the largest number." Confuses the size of a coefficient with which power of n grows fastest. n² will always overtake 100n eventually, no matter how large the 100 is.

✓

Right: "The time complexity is O(n²), since n² grows faster than n and eventually dominates every other term, regardless of the constants in front of them."

Linking question

How this connects to the rest of the syllabus

The IB syllabus is deliberately woven together, not a stack of isolated topics. Here's how Big O connects specifically to A4 (artificial intelligence).

A4

Is algorithmic efficiency relevant to machine learning, where large data sets are processed and computational cost can be significant? (Very directly: a machine learning model is typically trained on thousands or millions of records, so an algorithm inside that training process running in O(n²) instead of O(n log n) isn't a small difference, it's the difference between a model that finishes training overnight and one that doesn't finish at all. The same scalability reasoning this page applies to a photocopier room's queue applies just as literally to a data centre's training run, just at a scale where the gap between growth rates costs real time and real money.)

Revision questions

Past-paper style. Write an answer, then reveal the marking points and mark yourself.

Question 1 · 2 marks

[2]Explain what "time complexity" and "space complexity" each measure about an algorithm.

Question 2 · 3 marks

[3]An algorithm counts out to 2n² + 15n + 6 operations. State its Big O time complexity, and explain why the other two terms can be ignored.

Question 3 · 4 marks

[4]A school is deciding between two algorithms: one is O(n²) but simple to implement, the other is O(n log n) but more complex. Explain which one should be chosen if the school has 40 students, and which if it later grows to 4000, justifying your answer in terms of scalability.

Flashcards

Active recall for this statement’s key terms.