Big-O Without the Fear

Why this matters

Big-O has a reputation for being maths-heavy and interview-only. It is neither. It answers one practical question: when my data gets bigger, how much slower does this get? A page that is fine with 100 records and unusable with 100,000 has a Big-O problem, and you can see it coming without running anything.

What you'll learn

How to count steps instead of seconds, what the four common growth shapes look like with real numbers, how to read the shape off a piece of code, and when you can safely ignore all of it.

Count steps, not seconds

Seconds depend on your computer. Steps do not. Say n is the number of items. If the work is "look at every item once", that is about n steps, so doubling the data doubles the work. Big-O is just the habit of describing work as a function of n, and keeping only the part that dominates as n grows. A program that takes 3n + 7 steps is simply "O(n)", because for large n the 3 and the 7 stop mattering compared with the shape.

The four shapes you meet most

Read the last column slowly. A million items cost a million steps when linear, but a trillion when quadratic. That is why the difference decides whether something works at all.

Reading the shape from code

• One loop over the data is usually O(n).
• A loop inside a loop, both over the data, is usually O(n²). Each of the n items is compared with n items.
• Halving the problem each step (as in binary search) is O(log n). A million items need about 20 halvings, because 2 multiplied by itself 20 times is about a million.
• Jumping straight to an item by index or by key, as in an array or a hash table (what Python calls a dictionary or set), is O(1) on average.

Why data structures matter

The same question can have different costs depending on how the data is stored. "Is this name in my list?" on an unsorted list means checking items one by one: O(n). On a sorted list, binary search does it in O(log n). In a hash table or set, it is O(1) on average. The answer is identical; only the cost changes. This is the real reason to learn data structures, and it is the thread in Data Structures: How to Actually Start.

When to ignore it

For small n, the shape does not matter. Sorting 50 items any way you like is instant. Big-O starts to bite when n can grow: records in a database, rows in a file, users on a site. A sensible habit is to write the clear version first, and think about growth when the data can become large. If you are unsure, measure.

Try it yourself

In Python, this compares membership checks in a list and in a set of the same 100,000 numbers. Run it and compare the two times:

import time
n = 100_000
as_list = list(range(n))
as_set = set(as_list)
t = time.perf_counter(); [x in as_list for x in range(0, n, 50)]; print("list:", time.perf_counter() - t)
t = time.perf_counter(); [x in as_set for x in range(0, n, 50)]; print("set: ", time.perf_counter() - t)

Then double n and run it again. The list time should grow far faster than the set time. That gap is O(n) against O(1), measured on your own computer.

What's next

Put these shapes to work in Data Structures: How to Actually Start. If "an algorithm" still feels abstract, What Computer Science Actually Is shows where it fits in the bigger picture.

Continue learning

Mark this article as read

← Back to Guides