Learn to tell a single pass from a nested loop—and explain how their work grows.
Count the work, not the seconds
Imagine checking every name on a class list. With 10 names, you check 10 entries. With 100 names, you check 100. The amount of work grows with the list: this is linear growth.
Big O describes an upper bound on how an algorithm's work grows as its input grows. It does not tell you how many seconds your laptop will take.
One pass: O(n)
for name in names:
print(name)
For a list of n names, the loop runs n times. Assuming each print takes a fixed amount of work, doubling the number of names doubles the work. We describe this as O(n).
Every pair: O(n²)
for first in names:
for second in names:
compare(first, second)
For each of n names, the inner loop runs n times. That means n × n comparisons, assuming a comparison takes fixed work. Double n and you get four times as many comparisons.
Number of operations in these two examples
Names
One pass
Every pair
10
10
100
20
20
400
100
100
10,000
Two loops do not always mean n²
Two separate passes take n + n = 2n operations. Their growth is still linear, O(n). Two nested loops may be quadratic, but you need to check how often each one actually runs.
A tighter description for our single-pass example is Θ(n). Big O is an upper bound; when comparing these examples, we use their usual tight growth classes.
Explore the idea
Turn the input up. Watch the work grow.
Why do some algorithms do more work? Change the input, compare two loops, and see the difference in 3D.
for item in items:
visit(item)
8items → 8 operations. Double the input, double the work.
O(n)
Loading your 3D lesson…
One cube = one operation · Drag to explore
8 operations to explore
Your turn
Make the idea stick.
Try from memory, then compare your reasoning. Answers stay on this page and aren’t saved or graded.
2 practice questions01
A program scans a list of n names twice, in two separate loops. What is its growth class?
Try it in your own words
Compare with the explanation
O(n). There are 2n checks, so doubling the list doubles the work. The passes are separate, not nested.
02
The every-pair example makes 400 comparisons for 20 names. How many comparisons does it make for 40 names?
Try it in your own words
Compare with the explanation
1,600 comparisons. The two loops each run 40 times, so 40 × 40 = 1,600. Doubling the input quadruples the work.
Keep for later
Your reference sheet
The key ideas, ready when you need a refresher.
Open the reference sheet
O(n) · One full pass
n items need n fixed-work operations. Doubling n doubles the work.
O(n²) · Every pair
n outer iterations × n inner iterations. Doubling n quadruples the work.
Separate passes
Add their work. n + n = 2n grows linearly, so its usual tight growth class is O(n).
Count operations
Big O describes an upper bound on growth, not seconds on a particular computer.
Make it your course
Your materials. Your next small step.
Get a daily study plan, lessons built around your coursework, and space to ask Nova your own questions.
