2. Big-O: Measuring Speed"Fast" Means
The idea
Imagine a printed phone book with a million names in it, sorted A to Z. You need to find "Mehta".
The first way: start at page one and read every name until you hit Mehta. Worst case, a million steps.
The second way: open the book in the middle. You land on "L". Mehta comes after L, so throw away the whole first half. Open the middle of what is left. "R". Mehta is before R, throw away the second half. Keep halving. A million names becomes half a million, then a quarter million… after about 20 halvings you are holding one name. Twenty steps instead of a million.
Here is the halving trick on a sorted row of 16 numbers. Watch how much of the row goes grey after every single step:
Sixteen numbers, four looks. A million numbers would be twenty looks. That is the whole subject of "fast" in one picture. We do not time methods with a stopwatch, because a fast laptop and a slow phone would disagree. Instead we count steps, and we ask one question: when the list gets bigger, how much bigger does the step count get?
The list size is called N. The answer to that question is written in a shorthand called Big-O. You will say it out loud in every interview, so let's learn the six shapes it comes in.
The six shapes
O(1) — "constant". The same number of steps no matter how big the list is. Looking at box number 7 is one step whether the row has ten boxes or ten million. Picking the first item, adding two numbers, checking one box: all O(1).
O(log N) — "logarithmic". The phone-book trick. Each step throws away half of what is left. A million items takes about 20 steps; a billion takes about 30. When you see "sorted" in a problem, this shape is often available.
O(N) — "linear", or "one pass". You look at every box once. Finding the biggest price on the last page was O(N): five boxes, about five steps; a million boxes, about a million steps. Honest and usually fine.
O(N log N). A single pass, where each visit costs a phone-book lookup. This is the cost of a good sort. A million items takes about twenty million steps — still fast on a real computer.
O(N²) — "quadratic", or "every pair". For every box, you look at every other box. A loop inside a loop. Ten items is a hundred steps, fine. A million items is a trillion steps. This is the shape that fails interviews, and most of this course is about escaping it.
O(2^N) — "exponential", or "every combination". Trying every possible subset. Doubles with every extra item. Dead by N = 30. Only acceptable when N is tiny and the problem says so.
Watch it
Here is what those shapes cost, if the computer does a billion steps a second:
Read the last column top to bottom. The line between "instant" and "come back after lunch" sits between O(N log N) and O(N²). That line is where interviews are won.
How to count without thinking hard
You will rarely need to count exactly. Four rules cover almost everything:
- One loop over the list → O(N). You visited each box once.
- A loop inside a loop, both over the list → O(N²). Every pair.
- Halving each step → O(log N). Binary search, and anything shaped like a balanced tree.
- Two loops one after the other → still O(N). N + N is 2N, and we drop the 2. Big-O only cares about the shape of the growth, not the exact count. O(3N) is written O(N). O(N² + N) is written O(N²), because when N is big the N² part is all that matters.
The number the interviewer has in their head
Problems come with a size hint, like "N is up to 100,000". The interviewer already knows which shape passes. Roughly:
- N up to about 20 → O(2^N) is allowed. They want every combination.
- N up to about 1,000 → O(N²) is fine.
- N up to about 100,000 → you need O(N log N) or O(N). This is the common case.
- N up to 10 million or more → O(N) or O(log N). One pass, or the phone-book trick.
If your dumb solution is O(N²) and N is 100,000, you already know you are not done. That is useful. It tells you to keep looking before you write a line of code.
Space: the other cost
Time is steps. Space is the extra boxes you create while working.
If you keep a couple of variables, that is O(1) extra space — a handful of boxes, no matter how big the input. If you make a copy of the list, or a notebook with one entry per item, that is O(N) extra space.
Interviewers ask about both. The input list itself does not count; only what you add.
How to say it
One sentence, every time you finish a solution:
"This runs in O(N) time and O(1) space, because we walk the array once and only keep two variables."
Shape, then why. Say it even if nobody asks. It is the single easiest way to sound like you know what you are doing — because you will.
Practice
No problems yet. Go back to the find the biggest price code on the previous page and say its time and space cost out loud in the sentence above. (It is O(N) time, O(1) space: one walk, one extra box.)
In the room
Two slips lose points here. The first is guessing: saying "O(N)" without being able to point at the loop that makes it so. Always be able to say why. The second is forgetting space: a solution that copies the whole array is O(N) space, and the interviewer will ask whether you can do it in O(1). When they do, that is not a trick — it is an invitation to the next pattern.