Big O notation
A shorthand for how an algorithm's work grows as its input gets bigger.
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.
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.