Algorithms and Big-O without the heavy math
Why some code gets slow as data grows and some doesn't. What an algorithm is, how Big-O describes growth, the handful of classes you'll actually meet, and real timings that show the difference.
Two earlier parts left a promise. In part 6, a Fibonacci function made 242,785 calls where 26 were enough. In part 8, checking a set was about 46,000 times faster than checking a list. Both times the computer was the same. What changed was the algorithm. This part explains why, without more math than doubling a number.
What an algorithm is
An algorithm is “any well-defined set of instructions that when followed terminates after a finite number of steps that comprise a solution to a given computational problem.” A recipe for getting an answer.
The same problem usually has several algorithms. “Is this number in the collection?” can be answered by checking every item, by jumping to the middle of a sorted list, or by asking a set. All three are correct. They differ in how much work they do, and more importantly, in how that work grows when the data grows.
Big-O: how work grows
Measuring speed in seconds depends on the machine, the language, and what else is running. So instead we ask a simpler question: if the input doubles, what happens to the work?
That’s what Big-O notation describes. Wikipedia: “In computer science, big O notation is used to classify algorithms by how their run time or space requirements grow with the input.” The Python documentation uses it the same way: “to describe how the running time of an operation grows with the size of its inputs.”
You read O(n) as “order n”, where n is the size of the input. A few rules keep it simple:
- Only the growth matters.
O(2n)andO(n)are the same class; constants are dropped. - Only the biggest part matters.
O(n² + n)is justO(n²), because for large n then²part dominates. - It usually describes the worst case, unless someone says otherwise.
The classes you’ll actually meet
| Big-O | Name | If the input doubles… | Everyday example |
|---|---|---|---|
O(1) |
constant | work stays the same | look up a key in a dict, set, or map |
O(log n) |
logarithmic | work grows by one step | binary search in a sorted list |
O(n) |
linear | work doubles | go through every item once |
O(n log n) |
linearithmic | a bit more than double | a good sort |
O(n²) |
quadratic | work quadruples | a loop inside a loop over the same data |
O(2ⁿ) |
exponential | work squares (roughly) | naive Fibonacci, trying every combination |
The Python docs list these numbers for built-in operations. A few rows: for a list, x in l is O(n); for a set, x in s is O(1); for a dict, getting an item is O(1); sorting a list is O(n log n). The dict numbers are averages, which “assume the hash function for the objects is sufficiently robust to make collisions uncommon”, but in everyday code that holds.
Seeing it: quadratic vs linear
Here’s a common task: does a list contain any duplicates? A first attempt compares every item with every other item:
def has_duplicate_nested(items):
for i in range(len(items)):
for j in range(i + 1, len(items)):
if items[i] == items[j]:
return True
return False
A loop inside a loop over the same data: O(n²). Using the set from part 8 instead, each item is checked once:
def has_duplicate_set(items):
seen = set()
for x in items:
if x in seen:
return True
seen.add(x)
return False
One pass with O(1) checks: O(n). Timing both on lists with no duplicates (the worst case, since both must look at everything), on the machine used to write this note:
n nested (s) set (s)
1000 0.0093 0.000023
2000 0.0370 0.000045
4000 0.1537 0.000091
8000 0.6056 0.000237
Look at what happens each time n doubles. The set version roughly doubles: that’s linear. The nested version roughly quadruples: 0.009, 0.037, 0.154, 0.606. That’s quadratic. At 8,000 items it’s already over half a second; at 80,000 it would be about 100 times slower again, around a minute, while the set version would still finish in a few milliseconds.
This is why an O(n²) solution can pass every test with 20 rows and then time out in production with 50,000.
The same idea in PHP: in_array searches the array item by item (O(n)), while isset on an array key is a direct lookup. Flipping the array once with array_flip turns values into keys:
$ids = range(1, 1_000_000);
$lookup = array_flip($ids);
in_array(999_999, $ids); // ×100 → 0.0967 s
isset($lookup[999_999]); // ×100 → 0.000008 s
Seeing it: logarithmic
Binary search works on sorted data. It “compares the target value to the middle element of the array”, then throws away the half that can’t contain the target, and repeats. Counting the steps to find the last item:
binary search in 1,000 items: 10 steps
binary search in 1,000,000 items: 20 steps
binary search in 1,000,000,000 items: 30 steps
A thousand times more data, ten more steps. That’s O(log n), and it’s why “Binary search runs in logarithmic time in the worst case.” Python’s bisect module does this for you; it “provides support for maintaining a list in sorted order without having to sort the list after each insertion”:
import bisect
prices = [5, 12, 30, 45]
i = bisect.bisect_left(prices, 30)
print(i, prices[i] == 30) # 2 True
The catch: the data has to be sorted first, and keeping it sorted costs something. The bisect docs are honest about it: “the O(log n) search is dominated by the slow O(n) insertion step.” That trade-off is typical. Faster lookups usually cost something at insertion time or in memory.
Sorting: usually not your problem
Good general-purpose sorting is O(n log n), and you should almost never write your own. Python uses Timsort, which “can take advantage of any ordering already present in a dataset”, and its “Sorts are guaranteed to be stable”, meaning “when multiple records have the same key, their original order is preserved.” JavaScript’s Array.prototype.sort, PHP’s sort, and Go’s slices.Sort are all built-in and well tested. Use them.
Space counts too
Big-O also describes memory. The set-based duplicate check is faster because it keeps a set of everything it has seen, which costs O(n) extra memory. The nested version uses almost none. Memoization in part 6 was the same trade: remember answers (memory) to avoid recomputing them (time). Most performance improvements are a trade between the two.
How to use this without doing math
You rarely need to calculate Big-O formally. You need to recognize the shapes:
- A loop inside a loop over the same data → probably
O(n²). Ask whether a set or map could replace the inner loop. - Searching a list inside a loop (
if x in some_listinside afor) → the same problem in disguise. - A function calling itself twice per call with overlapping work → possibly exponential. Think memoization.
- Calling the database or an API inside a loop → the same shape, but each step costs milliseconds instead of nanoseconds. Fetch everything you need in one query instead.
- Sorting just to find the smallest or largest item →
min()/max()isO(n), sorting isO(n log n).
And the most important rule: measure before optimizing. Big-O tells you how code will behave as data grows; a quick timing tells you whether it matters at your actual size. A clear O(n²) loop over 50 items is fine.
Why this matters day to day
- Code that works in testing and dies in production is often an
O(n²)hiding behind small test data. - Reports and exports are where it usually shows up: matching orders to customers, products to stock, rows to rows.
- Database queries in loops are the same pattern at a much higher cost per step.
- Choosing a data structure is choosing an algorithm. Most fixes are “use a map/set instead of searching a list”.
Try it yourself
- Run the duplicate-check timing yourself and add
n = 16000. Predict both numbers before you run it. - Count how many binary-search steps it takes to find an item in 1,000,000,000,000 items. Then check with the code.
- Find a nested loop in your own code. Is the inner loop searching for something a map could look up directly?
- Write a function that returns the second-largest number in a list in
O(n), without sorting.
Summary
- An algorithm is a finite, well-defined way to solve a problem; the same problem usually has several.
- Big-O describes how work grows as input grows, ignoring constants and smaller terms.
- The common classes:
O(1),O(log n),O(n),O(n log n),O(n²),O(2ⁿ). - Measured: doubling the input doubled the linear version’s time and quadrupled the quadratic one’s.
- Binary search on sorted data: 1,000× more items, 10 more steps.
- Recognize the shapes (nested loops, search in a loop, queries in a loop), then measure before optimizing.
References
- Time complexity of operations on built-in types, Python documentation.
- bisect — Array bisection algorithm and Sorting Techniques, Python documentation.
- Algorithm, Big O notation, and Binary search, Wikipedia.