PYTHON / DATA STRUCTURES AND ALGORITHMS
Complexity, Big-O, and measuring real cost
Turn a Python function into a step count, name its Big-O class, and confirm the class with doubling tests and timeit measurements.
What you will learn
- Reduce a counted step total like n(n-1)/2 to its Big-O class
- Confirm a growth class by doubling n and reading the ratio of counts or times
- Measure with timeit over many repeats instead of one time.time() difference
- Distinguish worst case, average case, and amortised cost for the same function
Understanding Complexity, Big-O, and measuring real cost
Big-O describes the shape of a cost curve, not a duration. You pick a size parameter n, count how many times the dominant operation runs as a function of n, then keep only the fastest-growing term: 3n^2 + 500n + 20 is O(n^2), because at n = 10000 the n^2 term already accounts for over 98 percent of the total. Constants get dropped not because they are unimportant but because they do not change how the curve bends when n grows.
A single function has several honest complexities depending on which inputs you mean. Linear search over a list takes 1 step when the target is first, n steps when it is last or absent, and about n/2 steps averaged over all present targets, so an unqualified 'linear search is O(n)' is a worst-case claim. Amortised cost is a third thing again: list.append is O(1) amortised, yet the individual append that triggers a reallocation copies every existing element, so no single call is guaranteed cheap.
Big-O cannot predict runtime because it deliberately discards the constants that runtime is made of. In CPython a step of a Python-level loop costs tens of nanoseconds of interpreter overhead, while the per-element work inside a C-level scan such as `x in some_list` is a few nanoseconds, so for a few hundred elements the O(n) scan often beats a hand-written O(log n) binary search. The working method is therefore two-sided: use Big-O to rule out algorithms that cannot scale to your largest n, then use timeit at your actual n to choose among the ones that survive.
def linear_steps(data, target):
steps = 0
for value in data:
steps += 1
if value == target:
break
return steps
def binary_steps(data, target):
lo, hi, steps = 0, len(data) - 1, 0
while lo <= hi:
steps += 1
mid = (lo + hi) // 2
if data[mid] == target:
break
if data[mid] < target:
lo = mid + 1
else:
hi = mid - 1
return steps
print(f"{'n':>6} {'linear':>7} {'binary':>7}")
for n in (1000, 2000, 4000, 8000):
data = list(range(n))
print(f"{n:>6} {linear_steps(data, -1):>7} {binary_steps(data, -1):>7}")Big-O names how cost scales with input size, so it tells you which algorithm survives large n while only measurement tells you which is faster at your n.
Worked examples
A quadratic hiding in one line
Counting element copies shows that building a list with `result = result + [i]` is O(n^2) while append is amortised O(1).
def concat_copies(n):
copies = 0
result = []
for i in range(n):
copies += len(result) # every existing element is copied into the new list
result = result + [i]
return copies
for n in (100, 200, 400):
print(n, concat_copies(n))Example explained
Line 1`result + [i]` builds a brand new list, so it copies len(result) elements before adding one.
Line 2The totals are 0 + 1 + ... + (n-1) = n(n-1)/2, which is why 100 gives 4950.
Line 3Doubling n multiplies the copies by about four, the signature of O(n^2).
Line 4Replacing the line with result.append(i) makes the total copy count grow linearly instead.
Measuring instead of guessing
Uses timeit to compare a list scan against a set lookup and prints a stable verdict rather than raw seconds.
import timeit
list_time = timeit.timeit("target in data",
setup="data = list(range(20000)); target = -1",
number=200)
set_time = timeit.timeit("target in data",
setup="data = set(range(20000)); target = -1",
number=200)
print("list slower than set:", list_time > set_time)
print("ratio above 100x:", list_time / set_time > 100)Example explained
Line 1The `setup` string runs once per repeat group, so building the container is not timed.
Line 2`number=200` runs the statement 200 times, which lifts the total well above clock granularity.
Line 3A missing target forces the list scan through all 20000 elements, the O(n) worst case.
Line 4The set lookup does constant work, so the gap here is thousands of times, not a few percent.
Best, worst, and average for one function
The same linear search has three different step counts depending on where the target sits.
def steps_to_find(data, target):
for i, value in enumerate(data):
if value == target:
return i + 1
return len(data)
data = list(range(1000))
print("best (first element):", steps_to_find(data, 0))
print("worst (last element):", steps_to_find(data, 999))
print("absent target:", steps_to_find(data, -1))
print("average over all present targets:",
sum(steps_to_find(data, t) for t in data) / len(data))Example explained
Line 1Returning i + 1 counts the comparisons actually performed before the match.
Line 2The best case is constant and does not depend on n at all, so O(n) is a worst-case statement.
Line 3The average is (1 + 2 + ... + 1000)/1000 = 500.5, half the worst case, still linear in n.
Line 4An absent target costs the same as the worst present target, which is why absent keys dominate scan benchmarks.
Important notes
timeit disables the garbage collector while timing, so allocation-heavy code can look better under timeit than inside a real program.
Big-O says nothing about memory: an O(n log n) algorithm that allocates a second copy of the input can lose to a slower in-place one once the data no longer fits comfortably in RAM.
Common mistakes
Timing one call with time.time() and trusting the difference: on a fast operation the result is mostly clock granularity and cache warm-up, so a real 2x difference can appear as 20x or as zero.
Reading O(n^2) as 'never usable': for n around 20 to 50 an insertion sort with tiny constants routinely beats an O(n log n) algorithm with heavy setup, and reading O(1) as 'instant' hides constants like hashing a long key.
Calling `x in some_list` or `some_list.pop(0)` inside a loop over n and still describing the function as linear: each of those is itself O(n), so the real cost is quadratic and only shows up when the input grows.
Try it yourself
Change, predict, then run
Write a bubble sort that returns its comparison count, run it on list(range(n)) and on the reversed list for n = 100, 200, 400, and check that the counts roughly quadruple when n doubles.
Open the Python workspaceCheck your understanding
A function takes 0.40 s on 10000 items and 1.58 s on 20000 items. Which growth class fits best, and what should you conclude?
- O(n log n), since the time more than doubled
- O(n^2), since doubling n multiplied the time by about four
- O(n), since the time grew smoothly with n
- Nothing can be concluded, because Big-O says nothing about measured time
Show answer
Quadrupling the time for a doubled input is the fingerprint of a quadratic curve, so O(n^2) fits. O(n log n) is tempting because it does grow faster than linear, but doubling n there multiplies the time by only about 2.15, not 4; and while Big-O alone cannot predict a duration, ratios across doubled inputs are exactly how you infer the class from measurements.