# How time complexity actually grows when n gets big

Source: https://www.techinterview.org/post/3233476078/how-time-complexity-grows/
Updated: 2026-07-02 · techinterview.org

Double the size of the input and watch what the running time does. If it doubles, you're linear. If it barely moves, you're logarithmic. If it quadruples, you're quadratic, and you have a problem waiting for you at scale. That response to doubling is the whole content of Big-O notation, and it's the thing a whiteboard question is really checking.

The notation drops constants and lower-order terms on purpose. O(n) and O(100n) sit in the same class. People hate this the first time they see it, because a 100x slowdown obviously matters. It matters at a fixed size. Big-O is asking a different question: as n heads toward a million or a billion, which term wins? At that scale the n term buries any constant sitting in front of it, so the constant stops being the story.

## Where the curves cross

Take the most common tradeoff a coding interview pushes you toward: a brute-force O(n²) double loop versus an O(n log n) approach that sorts first, or an O(n) one that uses a hash map. The numbers are not close, and they get less close the bigger the input.

At n = 1,000 the quadratic version does a million operations and the linearithmic version does about ten thousand. Annoying, but survivable. Now make n a million. Quadratic does 1012 operations. The n log n version does about twenty million. On hardware that runs a billion simple operations a second, that's roughly seventeen minutes against two hundredths of a second. Same problem, same correct answer, wildly different afternoon.

That gap is why "can you do better than O(n²)?" is the most common follow-up in the building. The interviewer already knows your brute force works. They want to see whether you can find the structure that collapses the inner loop, which is almost always a hash map turning a repeated lookup from O(n) into O(1).


```
// O(n^2): for each element, scan the rest
for (int i = 0; i < n; i++)
  for (int j = i + 1; j < n; j++)
    if (a[i] + a[j] == target) return {i, j};

// O(n): remember what you've already seen
unordered_map<int,int> seen;
for (int i = 0; i < n; i++) {
  if (seen.count(target - a[i])) return {seen[target - a[i]], i};
  seen[a[i]] = i;
}
```

The phrasing barely changes between companies. You'll hear some version of:

- "What's the time and space complexity of that?"

- "Can you do better than O(n²)?"

- "Is that the average case or the worst case?"

## The growth table to keep in your head

Memorize the shape of the right-hand column, not the exact figures. The jump from one row to the next is the whole lesson.

| Class | Name | Shows up in | Cost at n = 1,000,000 |
| --- | --- | --- | --- |
| O(1) | constant | hash lookup, array index | 1 |
| O(log n) | logarithmic | binary search, balanced tree | ~20 |
| O(n) | linear | one pass over the data | 1,000,000 |
| O(n log n) | linearithmic | mergesort, heapsort, sort-then-scan | ~20,000,000 |
| O(n²) | quadratic | nested loops over the same array | 1,000,000,000,000 |
| O(2ⁿ) | exponential | every-subset brute force | hopeless past n ≈ 40 |
| O(n!) | factorial | every-permutation brute force | hopeless past n ≈ 13 |

## Why O(log n) barely counts as growth

Logarithmic time is so flat it hardly registers as growth at all. Binary search on a million sorted elements takes about twenty comparisons. On a billion it takes about thirty. Doubling the input adds a single step, because each step throws away half of what's left. Every balanced-tree operation and every sorted-array lookup rides on this property, which is why those data structures keep turning up the moment a problem says "find" or "the k largest." If you can turn a linear scan into a search over sorted or indexed data, you've usually found the intended answer.

## Constants are real, and the notation throws them away

This is where stronger candidates get more careful than the cheat sheet. For small n, the lower-complexity algorithm can lose. An O(n log n) sort with heavy per-element overhead runs slower than an O(n²) insertion sort when n is twenty. Production sorts are built around exactly this: introsort in C++ and Timsort in Python both fall back to insertion sort on small subarrays, somewhere around 16 to 32 elements, because the constant factor wins in that range.

So Big-O tells you who wins eventually, not who wins on your particular input. Process 50 items and the asymptotics are close to irrelevant, so pick the simpler code and move on. Process 50 million and the asymptotics are the only thing that matters. Saying that distinction out loud reads as someone who has shipped and profiled real code, rather than someone reciting a chart. Interviewers pick up on the difference fast.

## The classes that don't survive real input

Above quadratic, growth stops being a performance concern and turns into a wall. O(2ⁿ) shows up whenever a brute force tries every subset: the naive recursive subset-sum, the "include or exclude each element" decision tree. It's fine to sketch on a whiteboard for n = 20. At n = 40 you're staring at a trillion recursive calls. At n = 60 the program will not finish in your lifetime, no matter whose cloud you rent.

O(n!) is worse and turns up in permutation problems, the brute-force traveling salesman being the textbook case. 10! is about 3.6 million, still cheap. 13! crosses six billion. 20! is past 1018. The reason to recognize these on sight isn't to implement them, it's to know the instant you've written one, so you reach for dynamic programming, memoization, or a pruned search before the interviewer has to nudge you there.

## Quoting one number for an algorithm that has three

One of the quicker ways to lose points is to give a single complexity for an algorithm that has several. Quicksort is O(n log n) on average and O(n²) in the worst case, when the pivot keeps landing on the smallest or largest element. A hash map is O(1) average and O(n) worst, when every key collides into one bucket. Interviewers usually care about the worst case, because that's the guarantee you can actually make, but the real signal is that you know which case you're quoting and why. Name the case before they ask, and mention space while you're at it, since a slick recursive solution can quietly cost O(n) stack depth that a loop wouldn't.

If the curves still feel abstract, the fastest cure is to watch them move. Plotting n, n log n, and n² on the same axes makes the crossover obvious in a way a table never quite manages, and you can drag the input size around on the [Big-O visualizer](/big-o-visualizer/) or keep the [big-O cheat sheet](https://www.bigocheatsheet.com/) open while you grind problems. The growth class is the first thing you should be able to name about any solution, ideally before you write a single line of it.