How fast does the work grow?
Count the steps three small programs take for the same n: one loop, a loop inside a loop, and a loop that halves n. Double n and see one count double, one grow four times and one hardly move: a first look at Big O.
Core concept
The work a program does grows with its input: one loop over n items takes about n steps, a loop inside a loop takes n × n, and halving n each time takes only about log₂ n; Big O names this growth
Topic: Algorithm efficiency
Two programs can give the same answer but take very different amounts of work. To compare them we count their steps as the input n grows. A single loop: Steps that repeat, either a set number of times or until something becomes true. All key words FOR i FROM 1 TO n does its work n times. A loop inside a loop does the inner work n times for each of the n outer turns: n × n times. A loop that halves n each time, such as WHILE m > 1 DO m ← m ÷ 2, needs only a few turns, about log₂ n. Programmers write this growth in Big O notation: O(n) for the single loop, O(n²) for the nested loop and O(log n) for halving. For small n the difference is small, but when n doubles, n² grows four times, so a nested loop soon becomes slow.
What you will learn
- Count the steps of a single loop and of a nested loop for a given n.
- Predict how each count changes when n doubles.
- Explain why halving takes so few steps.
- Name O(n), O(n²) and O(log n) and say which grows fastest.
Before you start
- Know how for loops, nested loops and while loops repeat.
Materials
- A notebook for a table of n and the three counts
Equipment
- None
Procedure
- Run the program with n = 4 and read the three counts.
- Double n to 8 and compare the counts.
- Try n = 2.
- Answer the practice challenges.