A lesson from the data structures and algorithms bootcamp. About a 11 minute read.
Big-O describes how the work GROWS as the input grows, and deliberately throws away everything else. Understanding what it throws away is as important as knowing the ladder, because that is where the two classic mistakes live: quoting a bound you cannot justify, and optimising a constant that Big-O told you not to care about while the real problem was the shape of the loop.
O(f(n)) is an upper bound on growth: it means that beyond some input size, the work is at most a constant multiple of f(n). Two consequences follow and both are worth saying out loud. It is asymptotic, so it says nothing about small inputs, which is exactly why library sorts switch to insertion sort below about a dozen elements. And it is an upper BOUND, so O(n^2) is technically a true statement about a linear algorithm. Nobody says that in practice, because when people say O they usually mean Theta, a tight bound. Knowing the distinction is the difference between reciting the notation and understanding it, and interviewers do occasionally poke at it.
The rest of this lesson continues with 6 further sections. See the full curriculum.
Browse all 536 practice puzzles