# Big O notation

> A shorthand for how an algorithm's work grows as its input gets bigger.

- Level: Advanced
- Topics: Software
- URL: https://tidbit.legios.com.ar/big-o-notation/
- In Spanish: [Notación Big O](https://tidbit.legios.com.ar/es/big-o-notation/)

**Big O notation** describes how the running time (or memory) of an algorithm grows as the amount of data grows, ignoring the details of any particular computer. It does not say "this takes 2 seconds"; it says "if you double the data, this takes roughly twice as long" or "four times as long". Written as `O(n)`, `O(n²)` and so on, where `n` is the size of the input.

A few classes cover most everyday cases. `O(1)`, constant: reading item 500 of an array, or looking up a key in a hash table, takes about the same time no matter how much data there is. `O(log n)`, logarithmic: binary search on a sorted list of a million items needs only about 20 comparisons, because each step throws away half. `O(n)`, linear: checking every item once. `O(n log n)`: good general-purpose sorting. `O(n²)`, quadratic: comparing every item with every other item, fine for a hundred but painful for a million.

The notation describes the worst case and keeps only the part that dominates as `n` gets large, so `3n + 50` is simply `O(n)`. That is why it matters in practice: a quadratic piece of code that ran instantly in testing with 1,000 rows can bring a service to its knees in production with 1,000,000, because the work grew a million-fold rather than a thousand-fold. Engineers use Big O to compare approaches before writing them and to explain why something got slow.

## An analogy

Planning a party. Sending one group message is the same effort for 10 or 100 guests, O(1). Writing each guest a card grows with the guest list, O(n). Introducing every guest to every other guest explodes, O(n²).

## Keep in mind

- Describes growth of work as data grows, not exact seconds.
- Common classes: O(1), O(log n), O(n), O(n log n), O(n²).
- Only the dominant term counts: 3n + 50 is O(n).
- Explains why code that is fast in testing can crawl at real scale.

## Go deeper

- [Big O notation on Wikipedia](https://en.wikipedia.org/wiki/Big_O_notation)
- [Time complexity on Wikipedia](https://en.wikipedia.org/wiki/Time_complexity)

## Related terms

- [Algorithm](https://tidbit.legios.com.ar/algorithm/): A precise, step-by-step method for solving a problem or doing a task.
- [Hashing](https://tidbit.legios.com.ar/hashing/): A one-way fingerprint of data: easy to compute, not meant to be reversed.
