Module F-1 — Big-O Notation: Time and Space Complexity
What this module covers: Before any data structure or algorithm makes sense, you need a way to talk about cost that doesn't depend on which laptop you're running on. That's what Big-O notation is — not academic ceremony, but the same language you already use informally when you say an endpoint "doesn't scale." This module covers what Big-O actually measures, the complexity classes you'll see for the rest of this course, best/average/worst case, space complexity, and how to read cost directly off a block of code.
The Problem Big-O Solves
Say you write two functions that both find a value in an array. One takes 2ms on your machine, the other takes 5ms. Function one is faster — obviously.
Except: you tested with 100 items. Your laptop has 16GB of RAM and a fast SSD. Production runs on a smaller container, with 10,000 items, under load from other requests. "2ms on my machine" tells you almost nothing about how that function behaves at 10x, 100x, or 1000x the input size.
Big-O notation answers a different question: as the input grows, how does the cost grow? Not "how many milliseconds" — those depend on hardware, language, and what else is running. Big-O describes the shape of the cost curve, independent of all of that. It's the difference between "this car goes 60mph" (hardware-dependent) and "this car's fuel consumption doubles every time you double the speed" (shape-dependent, true on any car with that engine).
Analogy: Big-O is a shipping label, not a stopwatch. A label that says "doubles in weight for every doubled order size" tells you something a one-time weigh-in on a specific day never could.
Why this matters in production: every time you write a loop over user data, a query against a table, or a cache lookup, you're making an implicit bet about how that code behaves as the data grows. Big-O is how you check that bet before it ships — not after a customer with 50,000 rows in their account files a support ticket about a 30-second page load.
Time Complexity: Counting Operations, Not Seconds
Time complexity counts operations relative to input size, conventionally called n. It deliberately ignores constant factors (a modern CPU vs. an older one) and focuses on how the operation count grows as n grows.
Take this function:
typescript
In the worst case (the user is last, or not in the array at all), this checks every element once. Double the array, double the work. That's linear time, written O(n).
Now compare:
typescript
A Map lookup doesn't scan anything — it computes a hash and jumps straight to the bucket. Whether the map holds 10 users or 10 million, the lookup cost is roughly constant. That's O(1), and it's exactly why Module F-4 (Hash Maps) exists: this single difference is behind more real-world performance fixes than almost any other technique in this course.
The Common Complexity Classes
You'll see the same handful of shapes over and over. Here they are, ordered from cheapest to most expensive, with the growth if n goes from 10 to 10,000 (1000x the input):
Notation
Name
Operations at n=10
Operations at n=10,000
Example
O(1)
Constant
1
1
Hash map lookup, array index access
O(log n)
Logarithmic
~3
~13
Binary search, B-Tree index lookup
O(n)
Linear
10
10,000
A single loop over an array
O(n log n)
Linearithmic
~33
~133,000
Merge sort, quick sort (average case)
O(n²)
Quadratic
100
100,000,000
Nested loop over the same array
O(2ⁿ)
Exponential
1,024
effectively infinite
Naive recursive Fibonacci, brute-force subsets
Look at the jump between O(n) and O(n²) at n=10,000: 10,000 operations vs. 100 million. On a server handling that comparison per request, that's the difference between a response in milliseconds and a request that times out. This is the single most common cause of "it worked in the demo, it fell over in production" — the demo used a handful of rows, production doesn't.
typescript
hasDuplicatePair does roughly n × n comparisons — every element checked against every other element. Module F-4 shows how a hash set turns this exact function into O(n).
Best, Average, and Worst Case
The same algorithm can have different costs depending on the input, not just its size. findUser above is a good example:
Best case: the target is the first element — O(1) in practice, but this isn't the number you design around.
Average case: the target is somewhere in the middle — roughly n/2 checks, still O(n) once you drop the constant.
Worst case: the target is last, or missing entirely — n checks, O(n).
Big-O conventionally describes the worst case unless stated otherwise, because that's the bound you have to plan capacity around. A cache that's O(1) on hits but degrades to O(n) on hash collisions is, for planning purposes, an O(n) structure in the worst case — even if collisions are rare in practice. This distinction matters most for algorithms like quicksort (Module P-10), where the average case is O(n log n) but a specific worst-case input degrades it to O(n²).
Space Complexity: The Memory You Allocate
Big-O also measures memory, using the same notation. Space complexity counts extra memory the algorithm allocates, relative to input size — not the input itself, which you didn't choose to create.
typescript
sumInPlace uses one variable no matter how large nums is — O(1) space. doubleAll allocates a new array the same size as the input — O(n) space. Neither is "wrong" — but on a memory-constrained runtime (a serverless function with a 512MB or 1GB limit, for instance), the difference between transforming data in place and allocating a full second copy is the difference between a function that runs fine and one that gets OOM-killed once the input crosses a size nobody tested locally.
Recursion has a space cost too, easy to forget because it's not an explicit array or Map — it's stack frames. Module P-1 (Recursion and the Call Stack) covers this directly: a recursive function that goes n levels deep uses O(n) space on the call stack, even if it never allocates a single array.
Deriving Big-O From Code: A Quick Method
You don't need to count instructions precisely — you need to recognize shape. A practical method:
Find the loops. A single loop over n items is O(n). A loop inside a loop, each running over the same input, is O(n²) — unless the inner loop's range shrinks (like the j = i + 1 above), in which case it's still O(n²), just with a smaller constant.
Find the halving. If each step cuts the remaining problem in half (binary search, balanced tree descent), that's O(log n) regardless of how large n gets.
Find the recursive branching. If a recursive function calls itself twice per call with no memoization (naive Fibonacci is the classic case), the number of calls roughly doubles per level — O(2ⁿ). Module P-11 shows how memoization collapses this back down to O(n).
Drop constants and lower-order terms. A function that does 3n + 100 operations is still O(n) — the +100 and the 3× don't change the shape as n grows large, which is the entire point of Big-O.
typescript
When two costs are added together, only the largest one matters — O(n) + O(n²) is just O(n²), because at large n the quadratic term swamps the linear one entirely.
Where This Shows Up in Your Stack
Express/Next.js route handlers: a nested loop that cross-references two arrays from a request body (items.map(i => otherItems.find(...))) is O(n × m) hiding inside what looks like simple data-shaping code. It's invisible with 20 test items and a measurable latency spike with 2,000.
PostgreSQL: an index scan on an indexed column is O(log n) — the planner walks a B-Tree (Module A-13 covers this exact structure). A sequential scan, which happens when there's no usable index or the planner decides a full scan is cheaper, is O(n) — every row, every query.
Redis:GET/SET on a string key is O(1) — the reason Redis is reached for as a cache layer in the first place. Some Redis operations are not O(1) though — KEYS * and unbounded LRANGE are O(n), and running them against a large production dataset on the main thread is a well-known way to stall every other client.
Serverless functions (AWS Lambda, Vercel Functions): loading an entire dataset into an array before filtering it is O(n) space, not just O(n) time — and serverless memory limits are hard walls. A function that reads 50MB of rows into memory to filter them down to 200 works fine until the underlying table grows past the point where the unfiltered read fits in the container's memory limit.
Summary
Big-O measures growth, not seconds. It answers "how does cost scale as input grows," independent of hardware.
Time complexity counts operations relative to n. O(1) constant, O(log n) logarithmic, O(n) linear, O(n log n) linearithmic, O(n²) quadratic, O(2ⁿ) exponential — cheapest to most expensive.
Worst case is the default lens. Best/average case matter for intuition, but capacity planning is done against the worst case.
Space complexity counts extra memory allocated, including stack frames from recursion — not the input itself.
To derive Big-O from code: find loops (linear), nested loops (quadratic), halving (logarithmic), unmemoized recursive branching (exponential), and keep only the dominant term.
This shows up everywhere in production: route handler loops, Postgres index vs. sequential scans, Redis O(1) operations, and serverless memory ceilings.
The next module, Arrays: Memory and Access Patterns, builds directly on this — you'll see exactly why array indexing is O(1) and insertion/deletion isn't, in terms of how arrays are actually laid out in memory.
Knowledge Check
A function loops through an array of n items once, and inside that loop calls array.includes() to check for a value in a second array of the same size. What is the overall time complexity, and why?
A function reads all 500,000 rows of a database table into a JavaScript array before filtering it down to the ~200 rows that match a condition, then returns just those. What is the space complexity of this approach, and what is the practical risk?
According to the module, why does Big-O conventionally describe the worst case rather than the average case, even though the average case might be more common in practice?
Test your knowledge with more question sets
Sign in to access a wider variety of questions and get notified when new practice sets are added to this module.
functionfindUser(users: User[], targetId:string): User |undefined{for(const user of users){if(user.id === targetId)return user;}returnundefined;}
functionfindUserFast(usersById: Map<string, User>, targetId:string): User |undefined{return usersById.get(targetId);}
// O(n) — one passfunctionsumAll(nums:number[]):number{let total =0;for(const n of nums) total += n;// one loop, n stepsreturn total;}// O(n²) — nested pass over the same datafunctionhasDuplicatePair(nums:number[]):boolean{for(let i =0; i < nums.length; i++){for(let j = i +1; j < nums.length; j++){// for every i, loop the rest againif(nums[i]=== nums[j])returntrue;}}returnfalse;}
// O(1) space — a fixed number of variables, regardless of array sizefunctionsumInPlace(nums:number[]):number{let total =0;for(const n of nums) total += n;return total;}// O(n) space — allocates a new array proportional to the inputfunctiondoubleAll(nums:number[]):number[]{const result:number[]=[];for(const n of nums) result.push(n *2);return result;}
functionexample(nums:number[]):number{let total =0;for(const n of nums) total += n;// O(n)for(const a of nums){// O(n) ...for(const b of nums){// ... × O(n) = O(n²)if(a === b) total++;}}return total;// overall: O(n) + O(n²) → dominant term wins → O(n²)}