A lesson from the Algorithms & Patterns module of the bootcamp. About an 11 minute read.
Big-O describes how the work GROWS as the input grows, and it deliberately throws everything else away. Understanding what it throws away matters as much as knowing the ladder, because that is where the two classic mistakes live: quoting a bound you cannot justify, and optimizing 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 past some input size, the work is at most a constant multiple of f(n). Two things follow, and both are worth saying out loud. It is about large inputs, so it says nothing about small ones, 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 difference is what separates reciting the notation from 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 576 practice puzzles