Big-O Notation Explained for Beginners, With Python

Big-O notation answers one question: as the input gets bigger, how fast does the work grow? It doesn't tell you how many seconds a program takes. It tells you the shape of the growth, so you can predict what happens when a list of 1,000 items becomes a list of 1,000,000.

This is the topic of unit 15 in Encodr's Intro to Computer Science course, and it is a standard topic on CS1 finals. Every code example below is Python 3 and was run to confirm its output.

What Big-O measures

Big-O describes how an algorithm's running time (or memory use) grows as the input size, called n, grows. n is usually the length of a list or string.

Two simplifications make it work:

• Drop constant factors. 3n and 100n are both O(n). Doubling the input doubles the work either way.
• Drop lower-order terms. n^2 + n is O(n^2), and 3n + 7 is O(n). For large n, the biggest term swamps the rest.

Big-O is an upper bound on growth, not an exact count. That also means an O(n^2) algorithm isn't slower than an O(n) one for every input. For a small n, the O(n^2) one can win. Big-O is about what happens as n gets large.

Space complexity uses the same notation for extra memory instead of time.

The five classes you need

From slowest-growing to fastest-growing:

To feel the difference, here is roughly how many steps each class implies:

Going from a thousand items to a million multiplies the O(n^2) work by a million, but adds only about 10 steps to the O(log n) work.

Classifying loops: four rules

Most exam questions hand you a snippet and ask for its class. Four rules cover nearly all of them.

Rule 1: one loop over n is O(n)

``python n = 16 count = 0 for i in range(n): count += 1 print(count) # 16 ``

The body runs once per item, so the count equals n. Stepping by 2 doesn't change the class:

``python n = 16 count = 0 for i in range(0, n, 2): count += 1 print(count) # 8 ``

That's n / 2 iterations, and dropping the constant 1/2 leaves O(n).

Rule 2: nested loops multiply

``python n = 8 count = 0 for i in range(n): for j in range(n): count += 1 print(count) # 64 ``

The inner loop runs n times for each of the n outer passes: 8 x 8 = 64, so O(n^2).

A triangular loop, where the inner loop runs i times, is still O(n^2):

``python n = 16 count = 0 for i in range(n): for j in range(i): count += 1 print(count) # 120 ``

That's 0 + 1 + ... + 15 = 120, which is n(n - 1)/2. Drop the constant and the lower term and it's O(n^2).

But if the inner loop runs a fixed number of times, it's only a constant factor:

``python n = 16 count = 0 for i in range(n): for j in range(5): count += 1 print(count) # 80 ``

5n is O(n). The question is always whether the inner count grows with n.

Rule 3: loops one after another add

``python n = 16 count = 0 for i in range(n): count += 1 for j in range(n): count += 1 print(count) # 32 ``

n + n = 2n, which is O(n). If one block is O(n) and the next is O(n^2), the total is O(n + n^2), which simplifies to O(n^2). The largest term wins.

Rule 4: doubling or halving is O(log n)

``python n = 1024 count = 0 i = 1 while i < n: i *= 2 count += 1 print(count) # 10 ``

i goes 1, 2, 4, ... up to 1,024 in 10 steps, because 2^10 = 1,024. Multiplying or dividing the loop variable each pass (i *= 2, n //= 2) gives O(log n). Adding a constant (i += 3) is still linear.

Put a halving loop inside a linear loop and you get O(n log n):

``python n = 16 count = 0 for i in range(n): j = 1 while j < n: j *= 2 count += 1 print(count) # 64 ``

16 outer passes times 4 inner steps (log2 16 = 4) is 64.

Searching: why binary search is O(log n)

Linear search checks items one by one, so the worst case looks at all n. Binary search compares the target with the middle item and throws away the half where it can't be, so each comparison halves what's left:

```python def binary_search(items, target): lo, hi = 0, len(items) - 1 comparisons = 0 while lo <= hi: mid = (lo + hi) // 2 comparisons += 1 if items[mid] == target: return mid, comparisons elif items[mid] < target: lo = mid + 1 else: hi = mid - 1 return -1, comparisons

data = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91] print(binary_search(data, 23)) # (5, 3)

big = list(range(1_000_000)) print(binary_search(big, 999_999)) # (999999, 20) ```

Finding 23 takes 3 comparisons (indexes 4, 7, then 5). In a sorted list of a million items, this search takes 20. Doubling the list adds only about one more comparison. The catch: binary search only works on sorted data. Run it on an unsorted list and it can report "not found" for an item that's there.

A practical example: list versus set

Here are two ways to check a list for duplicates:

```python def has_duplicate_slow(items): for i in range(len(items)): for j in range(i + 1, len(items)): if items[i] == items[j]: return True return False

def has_duplicate_fast(items): seen = set() for x in items: if x in seen: return True seen.add(x) return False

print(has_duplicate_slow([3, 1, 4, 1, 5])) # True print(has_duplicate_fast([3, 1, 4, 1, 5])) # True ```

The slow version compares every pair: O(n^2). The fast version does one pass, and a membership test on a set is O(1) on average, so the whole thing is O(n). It pays for that speed with O(n) extra memory for the set, which is a time-for-space trade you will see again.

The same trap hides in a one-line test: if x in data inside a loop is O(n) per lookup if data is a list, so the loop becomes O(n^2). With a set, it stays O(n).

Sorting at a glance

Python's built-in sorted() is O(n log n).

How to get good at this

Big-O questions on exams are almost always "classify this snippet." The skill is pattern recognition, so practice on many short snippets rather than reading more explanations. Cover the answer, classify, then check, a loop that the testing effect shows works better than rereading notes. Mix in snippets from different patterns so you have to decide which rule applies; see interleaving vs blocking.

The doubling idea isn't unique to computer science. Economics asks how long a growing economy takes to double in size, and answers with the rule of 70, which comes up in what's in Principles of Macroeconomics. Security has its own growth-rate argument: defenses against brute-force password attacks work by increasing the work an attacker must do, one of many attack-and-defense topics on that exam; see how to study for Security+ SY0-701.

For the rest of the course, see what's in Intro to Computer Science and how to study for Intro to Computer Science. The free Intro to Computer Science flashcards include 82 cards in the searching, sorting and Big-O unit, and the course is one of Encodr's free gen-ed course flashcards.