Four Simple Rules
Turning "how many steps does this code do" into a Big O class takes four rules:
1. Keep the worst case — count the most steps the code can ever need.
2. Drop the constants — O(2n) and O(n/2) are both O(n).
3. Drop the smaller terms — O(n + n²) is O(n²).
4. Different inputs get different letters — two different lists give O(a · b), not O(n²).
Each rule has one example below.
Rule 1: Keep the Worst Case
A linear search can get lucky: if the value sits at the front, one step is enough. Big O ignores the luck and describes the list's worst case — the value is last, or missing, and all n elements are checked.
So a linear search is O(n), even though it often finishes earlier. The worst case is the promise the algorithm can always keep.
Best case and worst case of a search
Searching for the first word takes 1 step. Searching for a missing word takes all 5. Big O keeps the 5: linear search is O(n).
Output: complete Python program
def search(words, target):
steps = 0
for w in words:
steps += 1
if w == target:
break
return steps
words = ["one", "two", "three", "four", "five"]
print('best case ("one"):', search(words, "one"), "step")
print('worst case ("six"):', search(words, "six"), "steps")
Rule 2: Drop the Constants
A loop that visits every second element does n/2 steps. Half the work — but the shape of the growth is unchanged: double the input, double the steps.
Big O keeps only the shape, so O(n/2), O(n) and O(2n) are all the same class: linear.
Half the steps is still O(n)
The loop jumps by 2 and visits 4 of the 8 elements. If the list doubles, the steps double too — so n/2 steps is still linear growth, O(n).
Output: complete Python program
nums = [3, 1, 4, 1, 5, 9, 2, 6]
steps = 0
# Visit every second element: n/2 steps.
for i in range(0, len(nums), 2):
print(nums[i], end=" ")
steps += 1
print()
print("elements:", len(nums), "steps:", steps)
Rule 3: Drop the Smaller Terms
Code often mixes parts with different costs: a simple loop (n steps) followed by nested loops (n² steps). The total is n + n².
As n grows, the n² part swallows the rest — at n = 1000 it is a million steps against a thousand. Big O keeps only the fastest-growing term: O(n + n²) becomes O(n²).
n + n² steps
For 6 elements the simple loop adds 6 steps and the nested loops add 36 — 42 in total. The square term already dominates, and its lead only grows with n.
Output: complete Python program
nums = [1, 2, 3, 4, 5, 6]
steps = 0
# One simple loop: n steps.
for n in nums:
steps += 1
# A loop inside a loop: n * n steps.
for x in nums:
for y in nums:
steps += 1
print("n =", len(nums))
print("n + n*n =", steps)
Rule 4: Different Inputs, Different Letters
When nested loops run over two different inputs, the step count is a · b — the two lengths multiplied. Calling that O(n²) would be wrong: the inputs can have very different sizes.
The honest class is O(a · b). It only becomes O(n²) in the special case where both inputs are the same one.
Two different lists
3 colors times 2 animals is 6 steps. The complexity is O(a · b) — if the animals list grows and the colors list does not, only b matters.
Output: complete Python program
colors = ["red", "green", "blue"]
animals = ["cat", "dog"]
steps = 0
for c in colors:
for a in animals:
steps += 1
print("colors:", len(colors), "animals:", len(animals))
print("steps:", steps)
The Limits of Big O
Big O is a rough tool on purpose, and it is worth knowing what it hides.
It only sees the worst case. An algorithm with a scary worst case can be excellent in practice if that case is rare. Sometimes the average case is the number that matters.
It ignores the constants. On paper, 1000 · n and n are the same class. For small inputs, a "slower" O(n²) algorithm with tiny steps can beat a "faster" O(n) one with heavy steps.
Use Big O to compare how algorithms scale. For real speed on real data, measure.