Big-O and Why Complexity Matters | IT Foundations for Beginners

In this chapter

We'll learn to predict how code slows down as data grows — time and space complexity and Big-O — with five everyday pictures (a coat check, a dictionary, a guest list, sorting cards and everyone shaking hands), then measure the seat-map fix: from 8 seconds to 80 milliseconds.

16–18 min

The Problem in Real Life

Anna has the fix written: put the sold seat IDs into a Set, and check each seat with an instant lookup. Before she runs it, John stops her. "Predict it first. How much faster will it be?"

She shrugs. "A bit faster?" He takes the marker. "Let's count. Not seconds — steps. Then you'll never be surprised by a slow page again."

The question isn't "how fast is it today?" It's "what happens when the data gets ten times bigger?"

John

"It Works on My Test Data" vs. "How Does It Grow?"

Growth is the real question

Code that's fine with 200 items can be unusable with 20,000. What matters is how work grows.

Count steps, not seconds

Seconds depend on the computer. Counting steps shows the shape of the problem anywhere.

Loops inside loops

A loop inside a loop multiplies the work — the most common cause of slow code.

Big-O: How Work Grows as Data Grows

Time complexity describes how the number of steps an algorithm needs grows as the input grows. Space complexity describes how much extra memory it needs as the input grows. We describe both with Big-O notation, written like O(n), where n is the size of the input — for example, the number of seats.

Big-O doesn't measure seconds. It describes the shape of the growth: if the data doubles, does the work stay the same, go up a little, double, or explode? It also ignores small details and focuses on what dominates when n gets big. Here are the five shapes you'll meet most, each with an everyday picture:

O(1) — constant — the coat check: finding a coat by its ticket number takes the same time whether there are 10 coats or 10,000. The work doesn't grow at all. Examples: reading an array item by index, looking up a key in a hash table.
O(log n) — logarithmic — the dictionary: doubling the size of the dictionary adds just one more step, because each step halves what's left. A million items need about 20 steps; a billion need about 30. Example: binary search.
O(n) — linear — reading a guest list: to check every name on a list, the work grows exactly with the list. Twice the guests, twice the work. Examples: a loop through every item, linear search, adding up a cart.
O(n log n) — sorting cards the smart way: a little more than linear. This is what good sorting methods cost. Example: the built-in sort.
O(n²) — quadratic — everyone shakes hands with everyone: at a party where every guest shakes hands with every other guest, 10 guests make about 45 handshakes, but 1,000 guests make about 500,000. Double the guests, and the work becomes four times bigger. Example: a loop inside a loop over the same data.

Table — The five shapes of growth

Big-O	Name	Everyday picture	Example in code
O(1)	Constant	Coat check by ticket number	array[i], map.get(key), set.has(id)
O(log n)	Logarithmic	Searching a dictionary	Binary search
O(n)	Linear	Reading every name on a list	One loop over all items
O(n log n)	Linearithmic	Sorting a deck of cards smartly	The built-in sort
O(n²)	Quadratic	Everyone shakes everyone's hand	A loop inside a loop

Table — How many steps as the data grows? (rounded)

n (items)	O(1)	O(log n)	O(n)	O(n log n)	O(n²)
10	1	3	10	33	100
1,000	1	10	1,000	10,000	1,000,000
20,000	1	14	20,000	286,000	400,000,000
1,000,000	1	20	1,000,000	20,000,000	1,000,000,000,000

This whole line is a row — one record

At 20,000 items, O(n²) needs 400 million steps where O(n) needs 20,000. That is the seat map.

Table — The seat-map fix, measured

Version	How it checks "is this seat sold?"	Big-O	Steps (20,000 seats)	Load time
Old	Scan the array of 15,000 sold IDs for every seat	O(n²)	about 300,000,000	about 8.2 s
New	Instant lookup in a Set of sold IDs	O(n)	about 35,000	about 80 ms

This whole line is a row — one record

Before and after: the seat-map check

// Before: O(n²) — for every seat, scan the whole sold array
for (const seat of seats) {                     // 20,000 times
  seat.isSold = soldIds.includes(seat.id);       // scans up to 15,000 items each time
}

// After: O(n) — build a Set once, then each check is instant
const soldSet = new Set(soldIds);                // 15,000 steps, once
for (const seat of seats) {                      // 20,000 times
  seat.isSold = soldSet.has(seat.id);            // 1 step each time
}

The two versions look almost the same. The only difference is includes() on an array (a scan) versus has() on a Set (a coat-check lookup).

Counting the old seat-map code: for each of the 20,000 seats on the map, it walked through the array of 15,000 sold IDs to check if that seat was sold. A loop inside a loop — the handshake shape. In the worst case that's 20,000 × 15,000 = 300 million comparisons every time someone opens the page. With the small 200-seat club, it was only about 30,000 — which is why nobody noticed.

Counting the new code: first, put the 15,000 sold IDs into a Set: 15,000 steps, once. Then, for each of the 20,000 seats, one instant Set lookup: 20,000 steps. Total: about 35,000 steps. That's O(n) instead of O(n²) — around 8,000 times less work. She runs it: the seat map now opens in about 80 milliseconds instead of 8 seconds.

Space complexity — the price of the fix: the Set uses extra memory — about one more copy of the sold IDs. That's the trade-off: a little extra memory for a huge saving in time. This trade (spend memory, save time) is one of the most common in all of software, and it's usually worth it.

Performance awareness — what to actually do: you don't need to calculate Big-O for every line. Three habits are enough. Ask how big the data could get — 200 seats on a test is not 20,000 on Sale Day. Look out for loops inside loops over large data, and lookups done by scanning a list instead of a hash table. And measure before and after, as Anna did, instead of guessing. Most code is fast enough; the few slow spots matter enormously.

Key Takeaway

Big-O describes how work grows as data grows: O(1) stays flat (coat check), O(log n) barely grows (dictionary), O(n) grows in step (guest list), O(n log n) is good sorting, and O(n²) explodes (everyone shaking hands). A loop inside a loop over big data is the classic O(n²) trap — often fixed by using a hash table, trading a little memory for a huge saving in time.

Why This Matters

On Sale Day, 50,000 fans will open this page at the same time. With the old code, that's 50,000 × 300 million comparisons — no server could keep up. With the new code, it's easily handled. Big-O is how engineers spot that kind of disaster on a whiteboard, before customers do. A dedicated DSA course goes much deeper into analysing algorithms; the habits in this chapter are what every developer uses every day.

The stadium seat map opens in 80 milliseconds. Samantha opens it on her phone, on mobile data, and it's instant. "What did you change?" "One line," Anna says. "And the way I think about data." Time to prove it with four more BlueTicket features.