A. Programming Concepts and Skills · Algorithm Design and AnalysisMeasuring Efficiency: Run Times, Counting Steps and Big-O
C2.2 C2.3About 75 minutes
Learning goals- I can measure a program's run time with time.perf_counter() and explain why run times vary.
- I can count the statements, loop iterations or comparisons an algorithm performs as a function of n.
- I can describe growth with Big-O notation: O(1), O(log n), O(n), O(n log n), O(n²) and O(2ⁿ).
- I can tell the best case, worst case and average case of an algorithm apart.
Words to know
run time
How long a program takes to run on a particular computer, measured in seconds.
computational complexity
How the amount of work (steps or memory) an algorithm needs grows as the size of its input, n, grows.
basic operation
The step you count to measure work, usually the one inside the innermost loop, such as a comparison.
Big-O notation
A way to describe the growth rate of an algorithm's work, keeping only the fastest-growing term and dropping constant factors, e.g. O(n²).
worst case / best case
The input of size n that makes the algorithm do the most / the least work.
average case
The expected amount of work over all inputs of size n (often assuming every input is equally likely).
logarithm (base 2)
log₂ n is the power of 2 that gives n; roughly, how many times you can halve n before reaching 1.
Fast on your laptop, slow on the server
Two students write programs that check whether any two students in a school have the same student number. On a test file of 50 students, both programs finish instantly. Then the school board runs them on 2 million records. One finishes in under a second. The other is still running the next morning.
Both programs were correct. One was efficient and one was not. Curriculum expectations C2.2 and C2.3 ask you to compare algorithms "using run times and computational complexity analysis". This lesson gives you both tools; the rest of the unit uses them on searching, sorting and recursion.
Tool 1: measuring run time
Python's time.perf_counter() returns a very precise clock reading in seconds. Read it before and after the code you want to time, and subtract.
import time
def total(a):
s = 0
for v in a:
s += v
return s
for n in [100_000, 200_000, 400_000]:
data = list(range(n))
start = time.perf_counter()
total(data)
elapsed = time.perf_counter() - start
print(n, round(elapsed * 1000, 2), "ms")
Run it a few times. On one computer the output was 100000 2.2 ms, 200000 4.5 ms, 400000 8.56 ms. Your numbers will be different, but each should be roughly double the one before.
Run times are real and useful, but they have problems:
- They depend on the computer (a phone is slower than a desktop), the language and even the Python version.
- Other programs running at the same time add noise, so the same test can give different times. Run each test several times and keep the smallest time, or use the
timeit module, which does this for you. - They only tell you about the inputs you tried.
So computer scientists also count steps, which do not depend on the machine.
Tool 2: counting steps
Choose a basic operation: the step that is repeated most, usually the comparison or statement in the innermost loop. Then count how many times it happens for an input of size n. Add a counter to the code to check your count.
def has_duplicate(a):
"""Return (True or False, number of comparisons made)."""
comparisons = 0
n = len(a)
for i in range(n):
for j in range(i + 1, n):
comparisons += 1
if a[i] == a[j]:
return True, comparisons
return False, comparisons
for n in [10, 20, 40, 80]:
print(n, has_duplicate(list(range(n))))
Output, one line each: 10 (False, 45), 20 (False, 190), 40 (False, 780), 80 (False, 3160). The list range(n) has no duplicates, which is the worst case: every pair is compared. When n doubles, the count roughly quadruples.
Where does 45 come from?
Element 0 is compared with the 9 elements after it, element 1 with 8, and so on down to 1:
9 + 8 + 7 + … + 1 = 45, which is n(n − 1) ÷ 2 with n = 10.
You met this formula for selection sort in ICS3U (and it is the sum of an arithmetic series from MCR3U). For n = 2 000 000 it is about 2 × 10¹² comparisons. At a billion comparisons a second, that is more than half an hour, which explains the "still running" program.
Tool 3: Big-O notation
Exact counts like n(n − 1) ÷ 2 = 0.5n² − 0.5n are more detail than we need to compare algorithms. For large n, the fastest-growing term decides everything, and constant factors depend on the machine anyway. Big-O keeps only the growth rate:
- Find (or estimate) the step count as a formula in n.
- Keep the fastest-growing term and drop the others.
- Drop its constant factor.
So 0.5n² − 0.5n is O(n²), 3n + 7 is O(n), and 12 is O(1).
Formal definition: f(n) is O(g(n)) if there are positive constants c and n₀ such that f(n) ≤ c·g(n) for every n ≥ n₀. For example, 3n² + 5n + 2 ≤ 10n² for every n ≥ 1 (because 5n ≤ 5n² and 2 ≤ 2n² when n ≥ 1), so 3n² + 5n + 2 is O(n²) with c = 10 and n₀ = 1. University courses use this definition to prove growth rates; in this course you mostly use the three steps above.
| Big-O | Name | Typical example | n = 1000 | n = 1 000 000 |
|---|
| O(1) | constant | read a[i]; append to a list | 1 | 1 |
| O(log n) | logarithmic | binary search | about 10 | about 20 |
| O(n) | linear | linear search; sum a list | 1000 | 1 000 000 |
| O(n log n) | n log n | merge sort | about 10 000 | about 20 000 000 |
| O(n²) | quadratic | selection sort; compare all pairs | 1 000 000 | 10¹² |
| O(2ⁿ) | exponential | naive recursive Fibonacci | about 10³⁰¹ | a number with 301 030 digits |
Rules of thumb for reading code
- A fixed number of simple statements: O(1).
- A loop that runs n times with O(1) work inside: O(n).
- Nested loops multiply: n passes × n passes is O(n²). A triangle-shaped nested loop (j starts at i + 1) is still O(n²), because n(n − 1) ÷ 2 is half of n² minus a smaller term.
- Sequential parts add, and the biggest one wins: an O(n) loop followed by an O(n²) loop is O(n + n²) = O(n²).
- A loop that halves the remaining work each pass runs about log₂ n times: O(log n). (Logarithms are a unit of MHF4U; here you only need "how many halvings until 1".)
- Watch out for hidden loops:
x in a, a.index(x), a.insert(0, x), a.remove(x), sum(a) and slicing a[i:j] each loop over (part of) the list.
Worked exampleCounting steps and finding Big-O
Find the number of times count += 1 runs, as a formula in n, and the Big-O, for each fragment.
(a)
for i in range(n):
count += 1
for j in range(n):
count += 1
(b)
for i in range(n):
for j in range(n):
count += 1
(c)
k = n
while k > 1:
k = k // 2
count += 1
- (a) Two loops one after the other, each n times: n + n = 2n, which is O(n). (Sequential parts add.)
- (b) The inner loop runs n times for each of the n outer passes: n × n = n², which is O(n²). (Nested loops multiply.)
- (c) k is halved each pass. For n = 16: 16 → 8 → 4 → 2 → 1, which is 4 passes = log₂ 16. For n = 20: 20 → 10 → 5 → 2 → 1, also 4 passes. In general the count is the whole-number part of log₂ n, which is O(log n).
- Check with code: put each fragment in a function that returns count, and print it for several n.
(a) 2n, O(n). (b) n², O(n²). (c) about log₂ n (exactly the whole-number part of log₂ n for n ≥ 1), O(log n).
Best, worst and average case
The step count often depends on which input of size n you get, not just n.
has_duplicate([4, 4, 1, 7, 9]) finds the match on the first comparison: the best case, O(1).- A list with no duplicates makes it check every pair: the worst case, n(n − 1) ÷ 2, O(n²).
- The average case depends on what inputs are likely.
When people say "this algorithm is O(n²)" they usually mean the worst case, because it is a guarantee: it can never be slower than that. A program for an ambulance dispatcher or a bank cares about the worst case.
Constant factors still matter (a little)
Big-O says how the work grows. An O(n) algorithm that does 50 steps per element can be slower than an O(n²) one for n = 10 (500 steps against 100). But by n = 1000 the O(n) one does 50 000 steps against 1 000 000. For big inputs, the growth rate wins. Real libraries sometimes switch to a "slower" algorithm for small inputs for exactly this reason.
Just for funWhy do O(n²) algorithms never get invited to parties?
Every guest has to shake hands with every other guest, and with 100 guests that is 4950 handshakes before anyone gets to the snacks.
Hands-on activityThe doubling experiment
You need: a computer with Python, and paper for a table.
- Copy the
has_duplicate function from the lesson, but remove the comparison counter so it returns just True or False. - Time it with
time.perf_counter() on list(range(n)) (the worst case) for n = 1000, 2000, 4000 and 8000. Run each size three times and record the smallest time. - In your table add a column "time ÷ previous time". For an O(n²) algorithm, doubling n should multiply the time by about 4.
- Repeat with a linear algorithm:
has_duplicate_fast(a) that returns len(set(a)) != len(a). (Building a set is roughly O(n) on average.) What ratio do you see now? - Predict, then test: how long will the slow version take for n = 16 000? Were you within 20%?
What to look for: ratios near 4 for the nested-loop version and near 2 for the set version. Very small times (under a millisecond) are noisy, so trust the larger sizes more. If a run takes more than a minute, stop it with Ctrl+C.
Your turn
1Give two reasons why measured run times are not enough to compare algorithms.
They depend on the computer, language and other running programs (noise), and they only describe the inputs you happened to try. Step counts and Big-O are machine-independent.
2Simplify to Big-O: (a) 4n + 9 (b) 2n² + 100n + 3 (c) 25 (d) n + log₂ n
(a) O(n) (b) O(n²) (c) O(1) (d) O(n)
3How many comparisons does has_duplicate make in the worst case for n = 12?
4An O(n²) algorithm takes 3 s for n = 10 000. Estimate the time for n = 20 000 and n = 100 000.
Doubling n multiplies time by about 4: about 12 s. Multiplying n by 10 multiplies time by about 100: about 300 s (5 minutes).
5Why is if x in a: inside a for loop over a an O(n²) pattern?
x in a is itself a linear search (up to n comparisons), and it runs once for each of the n passes: n × n.
6What is the best case of has_duplicate, and how many comparisons does it make?
The first two elements are equal: it returns after 1 comparison, O(1).
7For n = 1024, how many times does the halving loop in Example (c) run?
More practice: warm-up
1What does time.perf_counter() return?
A precise clock reading in seconds; subtract two readings to get the elapsed time.
2Name the growth rate: O(n²), O(log n), O(1), O(n).
Quadratic, logarithmic, constant, linear.
3Order from slowest-growing to fastest-growing: O(n²), O(1), O(n log n), O(log n), O(n), O(2ⁿ).
O(1), O(log n), O(n), O(n log n), O(n²), O(2ⁿ).
4A loop runs n times with 3 simple statements inside. How many statements run, and what is the Big-O?
More practice: on your own
1Count the times count += 1 runs and give the Big-O:
n = 8
count = 0
for i in range(n):
for j in range(5):
count += 1
print(count)
The inner loop always runs 5 times, so 5n = 40 for n = 8. That is O(n): 5 is a constant, not a nested n.
2Count and give Big-O:
n = 6
count = 0
for i in range(n):
for j in range(i):
count += 1
print(count)
0 + 1 + 2 + 3 + 4 + 5 = 15 = n(n − 1) ÷ 2 for n = 6. Triangle-shaped nested loop: O(n²).
3An O(n log n) sort takes 0.02 s for n = 1 000 000. Using the table values (n log₂ n is about 20 000 000 for this n), roughly how many basic steps per second is the computer doing?
20 000 000 steps ÷ 0.02 s = about 10⁹ steps per second (a billion), which is typical for compiled code. (Python code is usually slower, closer to 10⁷ to 10⁸ simple steps per second.)
4Show that 5n + 20 is O(n) by giving constants c and n₀.
For n ≥ 1, 20 ≤ 20n, so 5n + 20 ≤ 25n. Take c = 25, n₀ = 1. (Other choices work, e.g. c = 6 and n₀ = 20, since 20 ≤ n then.)
5A function sums a list (O(n)) and then sorts it with selection sort (O(n²)). What is the Big-O of the whole function? Explain.
O(n²). Sequential parts add: n + n² is dominated by n² for large n.
Challenge
1Algorithm A takes 100n steps and algorithm B takes n² steps. For which n is A faster? What does this say about Big-O for small inputs?
A is faster when 100n < n², i.e. n > 100. For n < 100, B is faster; they tie at n = 100. Big-O describes large n; for small inputs constant factors can make the "worse" algorithm faster.
2Find the exact count and Big-O:
n = 16
count = 0
i = 1
while i < n:
for j in range(n):
count += 1
i = i * 2
print(count)
The outer loop runs for i = 1, 2, 4, 8 (4 times = log₂ 16), and each time the inner loop runs n = 16 times: 4 × 16 = 64. In general about n log₂ n: O(n log n).
3A doubling experiment gives times 0.5 s, 4.0 s and 32 s for n = 1000, 2000 and 4000. What growth rate does this suggest, and estimate the time for n = 8000.
Each doubling multiplies time by 8 = 2³, which suggests O(n³) (a triple-nested loop). n = 8000 would take about 32 × 8 = 256 s (over 4 minutes).
Quiz
1. Which is the best reason to use Big-O as well as measured run times?
2. Written in simplest form, what is the tightest Big-O of 7n² + 300n + 12?
3. A nested loop for i in range(n): for j in range(i + 1, n): runs its body how many times?
4. An O(n) program takes 2 s for n = 50 000. About how long for n = 200 000?
5. A loop halves k each pass, starting at k = n = 1 000 000. About how many passes does it make?
6. Which statement about the worst case is true?
Big idea: C2.2 and C2.3 ask students to compare algorithms using run times and computational complexity analysis, such as counting statements, loop iterations or comparisons. This lesson teaches both methods and the Big-O language used in every later lesson and in first-year university computer science.
How to help: Ask, "If the list were twice as long, how much longer would this take?" That one question captures Big-O. Handshakes make a good kitchen-table model: with 4 people there are 6 handshakes, with 8 people 28.
Common difficulties:
- Treating any nested loop as O(n²) even when the inner loop runs a constant number of times (that is O(n)).
- Forgetting hidden loops inside built-in operations such as
in, index, remove and insert. - Over-trusting one timing run. Encourage repeated runs and larger n.
- Confusing log₂ n with n ÷ 2. Halving once is n ÷ 2; halving until you reach 1 takes log₂ n steps.