Big O Notation Explained for Beginners with Python and JavaScript Examples

Submitted by jaypabs on Wednesday, November 11, 2026 - 17:32.

Your code works on your laptop with 20 test records. Then the school uploads 8,000 students, and the same page takes a full second to load. Nothing is broken; the algorithm simply does not scale. Big O notation is the tool programmers use to predict this before it happens. It sounds like math class, but the everyday version is simple: it describes how the amount of work grows when the input grows.

This guide explains Big O for beginners with small Python and JavaScript programs you can run yourself. Every output below is real, produced with Python 3.13 and Node.js 24. Your timings will be different on your computer, but the pattern will be the same, and the pattern is the whole point.

What Big O Notation Means

Big O answers one question: if the input becomes 10 times bigger, how much more work does my code do? We write it as O(something), where n is the size of the input, such as the number of items in a list or rows in a table.

We care about growth, not exact seconds. A faster computer changes the seconds but not the growth.
We usually describe the worst case, for example when the item you are searching for is the last one or not there at all.
We drop constants and small terms. A loop that does 3n + 5 steps is just O(n), because when n is a million, the + 5 and the 3 hardly matter compared to how the code grows.

The Common Big O Complexities

This short Node.js script prints how many basic steps each complexity needs as n grows:

// How many basic steps each complexity needs as n grows
const sizes = [10, 100, 1000, 10000];
const rows = sizes.map((n) => ({
  n,
  "O(1)": 1,
  "O(log n)": Math.ceil(Math.log2(n)),
  "O(n)": n,
  "O(n log n)": Math.ceil(n * Math.log2(n)),
  "O(n^2)": n * n,
}));
console.table(rows);

Output:

┌─────────┬───────┬──────┬──────────┬───────┬────────────┬───────────┐
│ (index) │ n     │ O(1) │ O(log n) │ O(n)  │ O(n log n) │ O(n^2)    │
├─────────┼───────┼──────┼──────────┼───────┼────────────┼───────────┤
│ 0       │ 10    │ 1    │ 4        │ 10    │ 34         │ 100       │
│ 1       │ 100   │ 1    │ 7        │ 100   │ 665        │ 10000     │
│ 2       │ 1000  │ 1    │ 10       │ 1000  │ 9966       │ 1000000   │
│ 3       │ 10000 │ 1    │ 14       │ 10000 │ 132878     │ 100000000 │
└─────────┴───────┴──────┴──────────┴───────┴────────────┴───────────┘

Read the table from top to bottom. When n goes from 10 to 10,000, O(log n) barely moves (4 to 14), O(n) grows 1,000 times, and O(n^2) grows a million times. Here is what each one looks like in real code:

O(1), constant: the work does not depend on n. Reading items[5], looking up a key in a dictionary or object, pushing to the end of an array.
O(log n), logarithmic: the problem is cut in half every step. Binary search, and database index lookups.
O(n), linear: one pass over the data. A for loop over a list, sum(), finding the maximum, x in some_list.
O(n log n): good sorting algorithms. Python's sorted() and JavaScript's Array.prototype.sort() are in this group.
O(n^2), quadratic: a loop inside a loop over the same data, such as comparing every item with every other item.

O(n^2) vs O(n): Finding Duplicates

A classic example: check whether a list of student IDs has any duplicates. The first version compares every pair. The second remembers what it has seen in a set, which can check membership in constant time on average:

import random
import time


def has_duplicate_slow(items):
    """O(n^2): compare every pair."""
    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):
    """O(n): remember what we have seen in a set."""
    seen = set()
    for item in items:
        if item in seen:
            return True
        seen.add(item)
    return False


def timed(func, data):
    start = time.perf_counter()
    result = func(data)
    return result, time.perf_counter() - start


print(f"{'n':>7} | {'slow O(n^2)':>12} | {'fast O(n)':>10}")
for n in [1_000, 2_000, 4_000, 8_000]:
    data = random.sample(range(n * 10), n)   # n unique numbers: the worst case
    r1, t1 = timed(has_duplicate_slow, data)
    r2, t2 = timed(has_duplicate_fast, data)
    assert r1 == r2 == False
    print(f"{n:>7} | {t1:>10.3f} s | {t2 * 1000:>7.2f} ms")

Output:

      n |  slow O(n^2) |  fast O(n)
   1000 |      0.015 s |    0.06 ms
   2000 |      0.059 s |    0.23 ms
   4000 |      0.242 s |    0.31 ms
   8000 |      0.919 s |    0.78 ms

Look at the slow column: each time n doubles, the time roughly quadruples (0.015, 0.059, 0.242, 0.919 seconds). That is the signature of O(n^2). At 8,000 items it already takes almost a second; at 80,000 it would take around 100 times longer. The fast version stays under a millisecond and grows roughly in step with n, with some noise because the numbers are so small.

The Hidden O(n): "in" on a List

Sometimes the slow loop is hiding in one innocent-looking keyword. In Python, x in my_list checks the items one by one, so it is O(n). Do it inside another loop and you have O(n^2) again. x in my_set uses hashing and is O(1) on average:

import time

n = 100_000
student_ids = list(range(n))
id_set = set(student_ids)
lookups = range(n - 1000, n)        # 1,000 lookups near the end of the list

start = time.perf_counter()
found = sum(1 for x in lookups if x in student_ids)     # O(n) per lookup
list_time = time.perf_counter() - start

start = time.perf_counter()
found2 = sum(1 for x in lookups if x in id_set)         # O(1) average per lookup
set_time = time.perf_counter() - start

print(f"list: found {found} in {list_time:.3f} s")
print(f"set:  found {found2} in {set_time * 1000:.3f} ms")

Output:

list: found 1000 in 0.414 s
set:  found 1000 in 0.056 ms

Same data, same answer, but the set version is thousands of times faster here. The same idea applies in JavaScript: array.includes(x) and array.indexOf(x) are linear, while set.has(x) and map.get(key) are fast lookups. If you check membership many times, build a Set or Map once and reuse it.

O(log n): Why Binary Search Is So Fast

If the data is sorted, you do not need to look at every item. Binary search checks the middle, throws away the half that cannot contain the target, and repeats. Instead of timing it, this program counts the steps:

def linear_search(items, target):
    steps = 0
    for i, value in enumerate(items):
        steps += 1
        if value == target:
            return i, steps
    return -1, steps


def binary_search(items, target):
    """items must be sorted. Halves the search range every step: O(log n)."""
    low, high, steps = 0, len(items) - 1, 0
    while low <= high:
        steps += 1
        mid = (low + high) // 2
        if items[mid] == target:
            return mid, steps
        if items[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    return -1, steps


for n in [1_000, 1_000_000]:
    data = list(range(n))
    target = n - 1                       # worst case for linear search
    print(f"n = {n:,}: linear steps = {linear_search(data, target)[1]:,}, "
          f"binary steps = {binary_search(data, target)[1]}")

Output:

n = 1,000: linear steps = 1,000, binary steps = 10
n = 1,000,000: linear steps = 1,000,000, binary steps = 20

A thousand times more data costs binary search only 10 extra steps. This is the same reason a database index makes a query fast: the index is a sorted structure (a B-tree), so the database can jump to the right rows instead of scanning the whole table. In real Python code, use the built-in bisect module rather than writing binary search by hand.

The Same Trick in JavaScript: Two-Sum

Here is a common interview and real-world problem: given a list of prices, is there a pair that adds up to exactly the budget? The nested loop checks every pair. The faster version asks, for each price, "have I already seen the price that would complete the pair?"

// Two-sum: is there a pair of prices that adds up to the budget?
function hasPairSlow(prices, budget) {        // O(n^2)
  for (let i = 0; i < prices.length; i++) {
    for (let j = i + 1; j < prices.length; j++) {
      if (prices[i] + prices[j] === budget) return true;
    }
  }
  return false;
}

function hasPairFast(prices, budget) {        // O(n)
  const seen = new Set();
  for (const price of prices) {
    if (seen.has(budget - price)) return true;
    seen.add(price);
  }
  return false;
}

const prices = Array.from({ length: 20000 }, (_, i) => i * 2 + 1); // all odd numbers
const budget = 3;  // odd + odd is always even, so no pair exists: the worst case
console.log(hasPairSlow([120, 45, 80, 35], 125), hasPairFast([120, 45, 80, 35], 125));

for (const fn of [hasPairSlow, hasPairFast]) {
  const start = performance.now();
  const result = fn(prices, budget);
  console.log(`${fn.name}: ${result} in ${(performance.now() - start).toFixed(1)} ms`);
}

Output:

true true
hasPairSlow: false in 117.9 ms
hasPairFast: false in 3.5 ms

Both functions give the same answers (the first line checks a small example where 45 + 80 = 125), but on 20,000 prices the Set version wins easily, and the gap grows quickly as the list gets longer.

How to Estimate Big O of Your Own Code

Find the loops. One loop over the input is O(n). A loop inside a loop over the same input is O(n^2). Two separate loops one after the other are still O(n).
Look inside the loop for hidden loops. in on a list, list.index(), array.includes(), array.find(), string concatenation in some languages, and calling a function that itself loops.
Watch for halving. If each step cuts the remaining work in half, think O(log n).
Count database calls too. Running one SQL query inside a loop over 1,000 rows means 1,000 round trips to the database (the "N+1 query" problem). One query with a JOIN or WHERE id IN (...) is usually much faster.
Measure when it matters. Big O tells you how code scales; a profiler or a simple timer tells you where the time actually goes.

Practical Tips

Do not optimize everything. For a list of 50 items, the simple O(n^2) version is fine and easier to read. Big O matters when data can grow: users, products, logs, transactions.
Pick the right data structure first. Most real speedups for beginners come from replacing a list search with a set or dictionary (Python) or a Set or Map (JavaScript).
Let the database do the work. Filtering, sorting and counting in SQL with proper indexes usually beats loading everything into PHP, Python or JavaScript and looping.
Memory has a Big O too. The fast duplicate check uses extra memory for the set. That trade (more memory, less time) is usually worth it, but it is a trade.
Use built-ins. sorted(), bisect, collections.Counter, Array.prototype.sort(), Set and Map are well tested and fast.

Conclusion

Big O notation is not about memorizing formulas. It is a habit of asking "what happens when this list gets 10 times bigger?" Remember the main shapes: O(1) and O(log n) barely notice growth, O(n) grows in step with the data, and O(n^2) explodes. Watch for loops inside loops and hidden searches like in on a list, reach for sets, maps and indexes, and your projects will stay fast long after the demo data is replaced by the real thing. Copy the examples above, change n, and watch the numbers for yourself.