Lesson 4: Big-O & complexity analysis
Imagine a huge phone book and you're hunting for one name: flipping page by page takes forever, but an alphabetized book gives a much smarter way in. This lesson gives that pattern a short name — Big-O — a handy way to describe how work grows with the amount of data. We'll meet three common cases: O
Big-O is simply asking: 'if you double the number of items, how much more work is that?'. If you go over every item once, doubling the items = double the work (we call this O(n)). If you compare every item against every item, doubling the items = four times the work (O(n²)). That's it — a short name for how fast the work grows.
- complexity analysis
- Estimating the work (time) and memory an algorithm needs as a function of the input size n.
- Big-O
- Notation for an algorithm's worst-case growth rate, ignoring constants and lower-order terms.
- linear time
- O(n): the work grows in direct proportion to the input size — one pass over each element.
