What Big-O means and the common growth rates

Big-O notation describes how much more work code does as its input gets bigger. This is called its time complexity. It keeps only the part that grows fastest and ignores fixed multipliers, so 3n² + 5n + 20 is simply O(n²).

Learn the common growth rates in order, with the kind of code behind each. O(1) takes the same few steps whatever the input. O(log n) cuts the problem in half at each step.

O(n) looks at every item once. O(n log n) is what good sorting costs. O(n²) compares every pair of items.

O(2^n) checks every possible subset. The gaps are huge: for a million items, O(n log n) is about 20 million steps, while O(n²) is a trillion.