What Big-O Means and Counting Steps
18 min · Intermediate
Need help? Ask a tutor on WhatsApp (opens in a new tab)A program that works on ten orders can crawl on a million. Big-O tells you why before you run anything. You count steps instead of seconds, because steps are the same on every computer.
Count steps, not seconds
Time complexity is how the number of steps a program takes grows as the input size n grows. It is counted in steps, not seconds, so it is the same on every computer.
Seconds change with every computer. The number of steps does not. Count how many times the main work repeats as the list grows.
def find_position(items, target): steps = 0 for index, item in enumerate(items): steps += 1 if item == target: return index, steps return -1, steps
orders = [40, 15, 90, 27, 63]print(find_position(orders, 90))print(find_position(orders, 99))Example 1 · Steps grow with the list
def find_position(items, target): steps = 0 for index, item in enumerate(items): steps += 1 if item == target: return index, steps return -1, steps
for n in (10, 100, 1000): items = list(range(n)) print(n, find_position(items, -1)[1])10 10 100 100 1000 1000
What this code does
- The target -1 is never present, so every item is looked at.
- The steps equal n each time: ten times more items, ten times more steps.
Finding 90 took 3 steps. The missing 99 took all 5 steps. The step count follows the length of the list.
Big-O keeps the fastest-growing part
Big-O notation describes how fast the step count grows, keeping only the fastest-growing term and dropping constants. A program with 3n + 10 steps is O(n).
A loop of n steps followed by another loop of n steps costs 2n. For large n the 2 does not change the shape of the growth, so we write O(n).
def two_passes(items): steps = 0 for _ in items: steps += 1 for _ in items: steps += 1 return steps
print(two_passes(range(1000)))print(two_passes(range(2000)))Example 2 · The small term fades
def work(n): steps = 0 for _ in range(n): steps += 1 for _ in range(n): for _ in range(n): steps += 1 return steps
for n in (10, 100, 1000): print(n, work(n), n * n)10 110 100 100 10100 10000 1000 1001000 1000000
What this code does
- work(n) is n steps plus n * n steps.
- As n grows the single loop barely matters. The total is close to n * n, so the cost is O(n²).
Doubling n doubled the steps, from 2000 to 4000. That straight-line growth is O(n).
Nested loops multiply
Quadratic time, written O(n²), means the steps grow with the square of n. Ten times more data means a hundred times more steps.
A loop inside a loop does n steps for each of n steps. That is n times n, not n plus n.
def count_pairs(items): steps = 0 for a in items: for b in items: steps += 1 return steps
print(count_pairs(range(10)))print(count_pairs(range(20)))Example 3 · Brute force: compare every pair
def has_duplicate_pairs(items): comparisons = 0 for i in range(len(items)): for j in range(i + 1, len(items)): comparisons += 1 if items[i] == items[j]: return True, comparisons return False, comparisons
for n in (10, 100, 1000): print(n, has_duplicate_pairs(list(range(n))))10 (False, 45) 100 (False, 4950) 1000 (False, 499500)
What this code does
- Checking every pair of order ids takes n * (n - 1) / 2 comparisons.
- With all ids different the loop never stops early: 45, 4950, then 499500.
- The constant 1/2 is dropped, so this is O(n²).
Example 4 · Better: remember what you have seen
def has_duplicate_set(items): seen = set() checks = 0 for item in items: checks += 1 if item in seen: return True, checks seen.add(item) return False, checks
for n in (10, 100, 1000): print(n, has_duplicate_set(list(range(n))))10 (False, 10) 100 (False, 100) 1000 (False, 1000)
What this code does
- A set answers "have I seen this?" in one step on average, so each item costs one check.
- The work is n checks, O(n), against 499500 for the pair loop at n = 1000.
Doubling n from 10 to 20 gave four times the steps: 100, then 400. That is O(n²).
Best case and worst case
Worst case is the input that makes a program do the most work, such as searching for a value that is not in the list. Big-O is usually stated for it.
The same code can be quick or slow depending on the data. A search that finds its target first stops at once. Big-O usually quotes the worst case, because that is the one you must survive.
ids = list(range(1, 1001))print(find_position(ids, 1)[1])print(find_position(ids, 1000)[1])print(find_position(ids, 5000)[1])Example 5 · Best case and worst case
def search_steps(items, target): steps = 0 for item in items: steps += 1 if item == target: break return steps
ids = list(range(1, 1001))print(search_steps(ids, 1), search_steps(ids, 500), search_steps(ids, 1000), search_steps(ids, 5000))1 500 1000 1000
What this code does
- Target 1 is the best case: one step.
- The middle value takes 500 steps. The last value and a missing value both take 1000.
Example 6 · One line can hide a loop
class Counted(int): calls = 0
def __eq__(self, other): Counted.calls += 1 return int.__eq__(self, other)
__hash__ = int.__hash__
items = [Counted(i) for i in range(500)]print(Counted(-1) in items)print(Counted.calls)Counted.calls = 0print(items.count(Counted(7)))print(Counted.calls)False 500 1 500
What this code does
- The class counts every == comparison Python makes.
inon a list compares item by item, so one missing value cost 500 comparisons.list.countalso checks every item. Short code is not cheap code.
The best case took 1 step. The last item and a missing item both took 1000 steps, the worst case.
Next step
Check your understanding
10 quick questions