CodeParkBig-O describes how the work grows when the input grows. You don't count exact steps. You ask: if the input gets 10 times bigger, how much more work does my code do?
Think of it like this: finding a name on a guest list. If you read every line, a list twice as long takes twice as long. Now say the list is sorted. You open it in the middle and throw away the half that can't hold the name, and you repeat that each time. Then doubling the list adds only one more look.
What we're measuring
We call the size of the input n. For an array, n is its length. For a string, n is the number of characters.
A step is one small piece of work: reading arr[i], adding two numbers, comparing two values. We count steps instead of seconds, because seconds depend on the laptop and steps don't.
Big-O is a label for how the step count grows with n. You read O(n) as "O of n". It means the steps grow in line with n: 10 times the input, 10 times the work.
One loop: O(n)
Here's a function that adds up an array. The loop body runs once per element.
With 5 elements that's 5 steps. With 1,000 elements it's 1,000 steps. The work grows exactly as fast as the input, so this is O(n), also called linear.
function total(nums: number[]): number {
let sum = 0;
for (const x of nums) {
sum += x; // runs n times
}
return sum;
}
A loop inside a loop: O(n²)
Now put one loop inside another. For every element, the inner loop walks over every element again.
With 3 elements that's 3 × 3 = 9 steps. With 1,000 elements it's 1,000,000 steps. The work grows with n × n, so this is O(n²) ("n squared"), also called quadratic.
Step through the trace below. Watch the steps counter: the inner pointer j does a full lap for each position of the outer pointer i.
function countAllPairs(nums: number[]): number {
let steps = 0;
for (let i = 0; i < nums.length; i++) {
for (let j = 0; j < nums.length; j++) {
steps++; // runs n * n times
}
}
return steps;
}
Halving each time: O(log n)
Some code throws away half of what's left on every step. You meet this when searching a sorted array: look at the middle, and you know which half the answer must be in.
Start with 16 items. After one step 8 are left, then 4, then 2, then 1. That's 4 steps. With 1,000,000 items it's only about 20 steps.
log n is the number of times you can halve n before you reach 1. Its full name is the logarithm of n, base 2. So this is O(log n), also called logarithmic. You don't need to calculate logs. Just remember that log of 1,000 is about 10, and log of 1,000,000 is about 20.
The trace looks for 13 in the numbers 1 to 16. Faded cells are the ones we've ruled out.
O(1) and O(n log n)
O(1), called constant time, means the work doesn't depend on n at all. Reading arr[5], arr.push(x), and map.get(key) are all O(1). An array of 10 items or 10 million: same cost.
O(n log n) is what good sorting costs. arr.sort() is O(n log n). Think of it as "a little more than one loop". Many solutions start with "sort the input first". Then the whole solution is at least O(n log n), because the sort alone costs that much.
The table to remember
Rough step counts for each growth rate. A computer does very roughly 100 million simple steps per second in JavaScript.
n = 10 n = 1,000 n = 1,000,000
O(1) 1 1 1
O(log n) ~3 ~10 ~20
O(n) 10 1,000 1,000,000
O(n log n) ~33 ~10,000 ~20,000,000
O(n²) 100 1,000,000 1,000,000,000,000
Read the last column. O(n) finishes in about a hundredth of a second. O(n log n) takes a fraction of a second. O(n²) takes around 3 hours. That gap is why interviewers care.
The rules for simplifying
Big-O keeps only the part that matters when n is huge.
- Drop constant numbers. Two separate loops over the array is 2n steps, written O(n). Doubling doesn't change the growth.
- Keep the biggest term. A nested loop plus one more loop is n² + n. When n is a million, the + n is tiny next to n², so it doesn't matter. Write O(n²).
- Loops one after another add. A loop, then another loop: O(n + n) = O(n).
- Loops inside each other multiply. A loop inside a loop: O(n × n) = O(n²).
- Different inputs get different letters. Looping over array
a(length n) then arrayb(length m) is O(n + m). A loop overbinside a loop overais O(n × m).
Time and space
Time complexity is how the number of steps grows. Everything above is about time.
Space complexity is how much extra memory your code uses as n grows. The input itself doesn't count, only what you create.
- A few variables (
sum,i,best) no matter how big n is: O(1) space. - A new array, Map or Set that can hold one entry per input element: O(n) space.
Often you can trade one for the other. Storing everything you've seen in a Set costs O(n) space but can turn an O(n²) search into O(n) time.
// O(1) extra space: only a couple of numbers, whatever the input size
function countEven(nums: number[]): number {
let count = 0;
for (const x of nums) if (x % 2 === 0) count++;
return count;
}
// O(n) extra space: the copy grows with the input
function doubled(nums: number[]): number[] {
const out: number[] = [];
for (const x of nums) out.push(x * 2);
return out;
}
Hidden loops in JavaScript
Some built-in methods look like one step but loop over the whole array inside. Put one of them in a loop and you've written a nested loop without seeing it.
arr.includes(x),arr.indexOf(x),arr.find(...): O(n), because they search from the start.arr.slice(),[...arr],arr.concat(): O(n), because they copy.arr.shift(),arr.unshift(x),arr.splice(i, 1): O(n), because every later element moves over by one.str.split(""),str + otherin a loop: O(n) each time.arr.sort(): O(n log n).
So for (const x of a) if (b.includes(x)) … is O(n × m), not O(n).
How the interviewer asks
After you write a solution, expect: "What's the time and space complexity?"
Answer with the Big-O and the reason, for both:
"It's O(n) time, because we visit each element once and each Map lookup is O(1). It's O(n) space, because in the worst case the Map holds every element."
You'll also hear "Can you do better?" That usually means: your solution is O(n²), and there's an O(n) or O(n log n) one. Look for the repeated work and remove it. Often it's an inner loop that searches.
Common mistakes
- Calling
arr.includes()inside a loop and saying O(n). It's a hidden inner loop, so the real cost is O(n²). - Saying two loops one after the other are O(n²). They add (n + n), so it's O(n). Only loops inside each other multiply.
- Writing O(2n) or O(n/2). Constants are dropped: both are O(n).
- Counting the input as extra space. If you only use a few variables, the space is O(1) even though the input array has n items.
- Forgetting the sort. If step one is
arr.sort(), the whole solution is at least O(n log n).