Why Data Structures and Big-O Matter

Choosing structures by their costs

A data structure organises data so that certain operations are efficient. The same task can take milliseconds or hours depending on the structure: checking whether an item is in a list of a million elements scans it (O(n)), while a set answers in O(1) on average. Big-O notation describes how running time or memory grows with input size n, ignoring constant factors: O(1) constant, O(log n) logarithmic (binary search, balanced trees, heaps), O(n) linear (one pass), O(n log n) (good sorting), O(n²) quadratic (nested loops over the data) and O(2ⁿ) exponential. Distinguish worst case, average case and amortised cost (the average over a sequence of operations, as with list.append, which occasionally resizes but is O(1) amortised). Space complexity matters too: an index can trade memory for speed. In Python, constant factors are larger than in C because every value is an object, so measure as well as reason, and remember that the built-in structures (list, dict, set, deque, heapq) are implemented in C and are usually faster than hand-written Python equivalents.

Growth rates

How running time grows with input size for common complexity classes.

Membership: list versus set

The same question with O(n) and O(1) average costs.

import time

n = 1_000_000
ids_list = list(range(n))
ids_set = set(ids_list)
queries = [n - 1, n // 2, -5] * 100            # 300 lookups, mostly near the end

start = time.perf_counter()
hits_list = sum(1 for q in queries if q in ids_list)   # each 'in' scans: O(n)
list_time = time.perf_counter() - start

start = time.perf_counter()
hits_set = sum(1 for q in queries if q in ids_set)     # each 'in' hashes: O(1) average
set_time = time.perf_counter() - start

print(hits_list == hits_set)                   # True: same answer
print(f"list: {list_time:.3f}s  set: {set_time:.6f}s")
# The set is typically thousands of times faster here; exact numbers depend on the machine.

Count the passes

A quick way to estimate complexity: one loop over the data is O(n); a loop containing a scan of the same data (like x in some_list) is O(n²). Replacing the inner scan with a set or dict lookup often turns minutes into milliseconds.

Quick check: What does amortised O(1) mean for list.append?

• Occasional resizes are expensive, but the average cost over many appends is constant
• Every append takes exactly the same time
• Append is O(n) always
• Append never allocates memory