--- title: "Big O notation explained simply" url: https://algopath.pro/blog/big-o-notation-explained-simply language: en summary: "Big O answers one question: if the input doubles, what happens to the work? Five shapes, and how to read them off your own loops." updated: 2026-10-15 --- # Big O notation explained simply **Short answer.** Big O notation answers one question. If the input doubles, what happens to the work? With O(1) it stays the same, with O(log n) it grows by one step, with O(n) it doubles, and with O(n²) it grows four times. Constants are dropped because only the growth rate matters on large inputs. Big O captures exactly that question. Everything else is [notation](https://en.wikipedia.org/wiki/Big_O_notation). ## Five shapes Doubling the input changes the running time in predictable ways. - **O(1)**: the work does not change. An array index. A hash map lookup. - **O(log n)**: the work goes up by one step. A million items takes 20 steps. Two million takes 21. - **O(n)**: the work doubles. One pass over everything. - **O(n log n)**: the work slightly more than doubles. Any decent sort. - **O(n²)**: the work goes up four times. Every pair. Five lines. They cover almost everything you will meet before graduate-level work. Which of them the input size allows is in [time complexity from the constraints](/blog/time-complexity-from-constraints). Every term used here is defined in the [glossary](/glossary). A fuller table per data structure is the [Big-O cheat sheet](https://www.bigocheatsheet.com/). ## Why constants get dropped A loop doing three things per element is O(n). So is a loop doing one thing. That feels wrong. Three times slower is three times slower. Big O answers a different question. How does this behave as the input grows without bound? A constant of three stays three forever. Going from n to n squared runs away. At a million, that is 3 million steps against a trillion. The constant stops being interesting. ## Reading it off your own code Three rules get you most of the way. **A loop over the input is n.** A loop inside a loop is n squared. Nesting multiplies. **Halving is log n.** Each pass throws away half of what is left. Binary search is the clearest example of halving. It is also why balanced trees are fast. **Sequential steps add, and addition keeps the larger.** Sort plus one pass is n log n plus n. That is n log n. The trap is a hidden loop. A method that scans a string inside your loop makes it quadratic. No second set of braces on screen. Call something inside a loop, ask what it costs. ## Space works the same way Same question, applied to memory. Double the input, how much more do you store? A few variables is O(1). A copy of the input is O(n). A table of every pair is O(n²). That last one runs out of memory first in practice. Interviewers ask for both. Answer only time, and you drop a point you had earned. Saying the space cost out loud is [thinking out loud](/blog/how-to-talk-during-a-coding-interview). ## Where the notation lies Two honest caveats. At small sizes the constants win. [Insertion sort](https://en.wikipedia.org/wiki/Insertion_sort) beats [quicksort](https://en.wikipedia.org/wiki/Quicksort) under about 20 elements. Real implementations switch to it at the bottom. Memory layout matters too. Walking an array beats walking a linked list of the same length. Both are O(n). One sits in [cache](https://en.wikipedia.org/wiki/CPU_cache). The other does not. Big O picks the algorithm. Measurement picks the implementation. You need both. The [Big O calculator](/big-o-calculator) times your own function at growing sizes and names its class. ## Where this sits in the track [AlgoPath](/) puts complexity in step 08, ["Why some ways are faster"](/steps/why-some-ways-are-faster), before any pattern. Every later step states its cost and expects you to read it. Why this is one of five missing pieces is in [why algorithm problems are hard](/blog/why-are-algorithms-so-hard). The first 33 steps are free.