Big O

A way to describe how much slower or bigger a program gets as its input grows.

What is it?

Two solutions to the same problem can both "work," but behave very differently once the amount of data grows. One might stay fast with a million items; another might crawl to a halt. Big O notation is a way to describe that growth pattern — how the time (or memory) a program needs scales as the input gets bigger — without depending on the exact hardware it runs on.

You'll see it written like O(1), O(n), or O(n²), where n represents the size of the input.

Explain like I'm 10

Imagine looking up a word in a dictionary versus checking every page one by one. Both find the word eventually, but one gets dramatically slower as the dictionary grows, and the other barely changes. Big O is how we describe that difference.

Examples

O(1) vs O(n)

// O(1) — constant time: same speed no matter the array size
function getFirst(arr) {
  return arr[0];
}

// O(n) — linear time: gets slower as the array grows
function findValue(arr, target) {
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] === target) return i;
  }
  return -1;
}

getFirst always does exactly one step. findValue might need to check every single item, so its worst-case work grows directly with the array's size.

How it works

Big O describes the shape of growth, ignoring constant factors and small details. O(1) means the work stays the same regardless of input size. O(n) means the work grows in direct proportion to the input. O(n²) means the work grows by the square of the input — often caused by a loop nested inside another loop over the same data.

Input size (n) grows →

O(1)   ▬▬▬▬▬▬▬▬▬▬  (flat — stays fast)
O(n)   ▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬  (grows steadily)
O(n²)  ▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬  (grows steeply)

Why does it exist?

As soon as data gets large — thousands or millions of items — the difference between an efficient and inefficient approach becomes the difference between an app that feels instant and one that visibly freezes. Big O gives engineers a common language to compare approaches before writing (or after debugging) real code.

When to use it

Reach for Big O whenever you're choosing between two different approaches to the same problem and need a fast way to compare how they'll scale, or when you're explaining — in an interview or a code review — why one solution is better than another.

When not to use it

For truly tiny, fixed-size inputs that will never grow, the difference between O(n) and O(n²) may not matter in practice — don't let Big O turn into premature optimization for code that never runs on real-sized data.

Common mistakes

  • Assuming code that works fine on a small test array will work fine at real scale.

  • Confusing best-case performance with worst-case — Big O usually describes the worst case.

  • Ignoring nested loops over the same data, which is one of the most common causes of O(n²) code.

Practice exercises

  1. Easy:

    Identify the Big O of a function that returns array.length.

  2. Medium:

    Identify the Big O of a function with one loop that checks every item in an array, and explain why.

  3. Hard:

    Identify the Big O of a function with a loop inside a loop, both running over the same array, and explain what causes the extra cost.

Interview questions

What does Big O notation measure?

How the running time or memory usage of an algorithm grows as the input size increases, independent of the specific hardware.

What's the difference between O(n) and O(n²)?

O(n) work grows directly with input size; O(n²) work grows with the square of it — usually from a loop nested inside another loop over the same input.

Is Big O about the best case or the worst case?

Usually the worst case, since that's the guarantee you can rely on — though best-case and average-case notations exist too.

Why is `O(2n)` simply written as `O(n)` in Big O notation?

Because Big O describes the shape of an algorithm's growth as input size increases, not its exact runtime — multiplying by a constant (like 2) scales the line up or down but doesn't change whether it's flat, linear, quadratic, etc. Constant factors are dropped so Big O reflects the scaling behavior, not machine-specific speed.

Why is `O(n² + n)` simplified to just `O(n²)`?

Because as n gets large, the n² term grows so much faster than the n term that the n term becomes negligible by comparison — Big O keeps only the dominant (fastest-growing) term and drops lower-order ones, since they don't affect the long-term growth trend.

What is `O(log n)`, and what kind of code produces it?

Logarithmic time: the work needed grows very slowly as n increases, because each step eliminates a large fraction (often half) of the remaining input rather than processing it one item at a time. Doubling the input size only adds roughly one extra step, instead of doubling the work.

Why is binary search `O(log n)`?

Each comparison against the middle element eliminates half of the remaining search space, so after k comparisons only n / 2^k elements remain; solving for when that shrinks to 1 element gives k = log2(n) — the number of comparisons needed grows logarithmically, not linearly, with n.

What is `O(n log n)`, and where does it typically show up?

It's the complexity of efficient comparison-based sorting algorithms, like merge sort (always) and quicksort (on average): the data is repeatedly split in half (log n levels of splitting), and at each level roughly n total work is done merging or partitioning — multiplying n work per level by log n levels gives O(n log n) overall.

What causes an algorithm to be `O(2ⁿ)`, and what's a classic example?

Exponential time typically comes from a recursive function where each call branches into multiple further calls that each explore a large portion of the problem again, without reusing prior work. The classic example is naive recursive Fibonacci: each call to fib(n) makes two more calls, fib(n-1) and fib(n-2), and this branching roughly doubles the number of calls made at each level.

What is `O(n!)`, and when does it come up?

Factorial time — the number of operations grows by the factorial of the input size, which is even faster-growing than exponential. It shows up in problems that must consider every possible ordering (permutation) of n items, since there are n! distinct permutations to generate or check.

What's the difference between time complexity and space complexity?

Time complexity describes how an algorithm's running time grows as input size increases; space complexity describes how much extra memory it needs as input grows. An algorithm can be fast but memory-hungry, or slow but memory-efficient — they're measured independently.

When an interviewer asks for an algorithm's space complexity, does that include the input itself?

Usually not — interviewers typically mean auxiliary space: the extra memory an algorithm allocates beyond the input it was given (like temporary variables, new data structures, or recursion stack frames), not the space the input already occupies.

What does `O(1)` space mean, and what's an example?

It means the amount of extra memory used stays constant no matter how large the input grows. Swapping two variables using a temporary variable, or a loop that only tracks a running total and an index, both use a fixed, small number of variables regardless of input size.

Why can a recursive function have hidden space costs even if it doesn't create any new arrays or objects?

Every recursive call adds a new frame to the call stack to track its local variables and where to resume after the call returns. If a function recurses to a depth of n, that's n stacked frames sitting in memory at once — so recursion depth alone can make an algorithm O(n) space, even with no explicit data structure involved.

A recursive factorial function and an iterative loop-based one are both `O(n)` time — are they equal in space complexity too?

No. The iterative version uses O(1) extra space — just a counter and a running result. The recursive version uses O(n) extra space, because each of the n recursive calls stays on the call stack until the base case returns and the calls unwind — same time complexity, different space complexity.

What is the time complexity of `for (let i = 0; i < n; i++) { for (let j = 0; j < n; j++) { total++; } }`?

O(n²) — the inner loop runs n times for every one of the n iterations of the outer loop, so the total number of iterations is n × n = n², regardless of what work happens inside.

What is the time complexity of running two separate, non-nested loops back to back, each looping from `0` to `n`?

O(n) — even though there are two loops, neither is nested inside the other, so the total work is n + n = 2n; Big O drops the constant factor, leaving O(n), not O(n²).

Is `array.push()` always `O(1)`? What's happening when it occasionally seems slower?

It's amortized O(1). Most pushes just write to the next open slot and increment length — truly O(1). But when the array's underlying allocated capacity is full, the engine must allocate a larger block of memory and copy every existing element into it, which is O(n) for that one push. Because capacity typically grows by doubling, these expensive resizes become exponentially rarer, so averaged over many pushes, the cost per push still works out to O(1).

If a loop runs `n` times, and each iteration calls `array.includes()` (itself O(n)) on an array of size n, what's the overall time complexity — and why is it not just O(n)?

O(n²) — describing only the outer loop as "O(n) because it runs n times" ignores the cost of what happens inside each iteration; here each of the n iterations does O(n) work, so the total is n × n = O(n²).

If an outer loop runs `n` times but its nested inner loop always runs exactly 5 times regardless of `n`, what's the overall time complexity?

O(n) — the inner loop's iteration count doesn't depend on n at all, so it's a constant factor (5×) that gets dropped; only the outer loop's n iterations affect the growth rate.

For a nested loop where the inner loop is `for (let j = i; j < n; j++)` inside an outer `for (let i = 0; i < n; i++)`, what's the time complexity, even though the inner loop gets shorter each pass?

Still O(n²) — the total number of inner-loop iterations across all outer passes is n + (n-1) + (n-2) + ... + 1, which sums to n(n+1)/2; that's a quadratic expression, and Big O keeps only the dominant n² term, dropping the rest.

Why is a hash table lookup typically `O(1)` while searching an array for a value is `O(n)`?

An array search has no way to know where a value is, so it must check elements one by one in the worst case. A hash table computes a numeric index directly from the key using a hash function, then jumps straight to that slot — turning a search into a direct calculation instead of a scan, trading extra memory (for the hash table's internal storage) for that speed.

Is a hash table lookup guaranteed to be `O(1)`?

Only on average, assuming a good hash function spreads keys evenly. In the worst case — many keys hashing to the same bucket (a collision-heavy scenario) — a hash table can degrade toward O(n), since it has to scan through all the colliding entries in that bucket, similar to a linked list search.

If most everyday programs run on fast hardware, why do interviewers care so much about Big O?

Real systems often operate on large datasets — thousands to billions of records — where the difference between, say, O(n log n) and O(n²) is the difference between a query returning in milliseconds versus taking hours on the exact same hardware. Big O predicts which approach will hold up as data grows, which is exactly the scenario where performance problems actually surface in production.

What does it mean for Big O to be "asymptotic"?

It describes how an algorithm behaves as the input size grows arbitrarily large (approaches infinity), deliberately ignoring constant startup costs and behavior on tiny inputs. Two algorithms can perform almost identically on a 5-element input yet diverge enormously at a million elements — Big O is about that long-term trend, not any one specific input size.

Can two algorithms with the same Big O complexity have very different real-world speeds?

Yes. Big O hides constant factors: an O(n) algorithm doing 1 operation per element and another O(n) algorithm doing 100 operations per element are both "O(n)", but the second will run roughly 100x slower in practice. Big O compares how work scales, not the actual wall-clock time for a given input.

What's the difference between Big O, Big Omega, and Big Theta?

Big O describes an upper bound on growth (it won't get worse than this); Big Omega describes a lower bound (it won't do better than this); Big Theta describes a tight bound, where the upper and lower bounds match. In everyday interview usage, "Big O" is often used loosely to mean the typical/tight bound, but formally it's specifically an upper bound.

Insertion sort is often described as O(n²) — is that always true?

That's its worst case (e.g. a reverse-sorted array), where each new element must shift past every previously sorted element. Its best case is O(n): if the array is already sorted, each element only needs one comparison against its neighbor and no shifting, so the algorithm makes a single pass.

Why is reading `array.length` in JavaScript O(1) instead of counting every element?

JavaScript arrays maintain length as a property that's automatically kept up to date whenever elements are added or removed (via push, pop, direct assignment, etc.), so reading it is just a direct property access — not a recount of the elements.

Could an algorithm with worse Big O complexity actually run faster than a better one in practice? When?

Yes, for small enough input sizes. Big O ignores constant factors, and an algorithm with better asymptotic complexity (like O(n log n)) can have more overhead per operation than a simpler O(n²) approach; for small n, that overhead can outweigh the asymptotic advantage. This is why some real sorting implementations switch to simple insertion sort for small sub-arrays even inside an overall O(n log n) algorithm.