Big O in plain english

12/11/2013

This answer on stack overflow is one of the nicest explanations I’ve seen of the Big O notation used in software engineering. However, this other answer easily wins for best example; using various activities you’d perform on a phone book to explain different complexities is genius.

(Quick recap: Big O notation is used to capture the upper bound of the complexity of an algorithm, Big Ω is used for lower bound, and Big Θ for upper and lower, or “tight”, bound. For Big-O complexities of common algorithms used in computer science, check out the fantastic Big-O cheat sheet.)

I’ve paraphrased the phone book example below since I liked it so much. Note that the input “n” here is the number of pages in the phone book.

O(1): Given a person’s name and the page that the person is listed on, find their phone number. This is a constant-time operation, since flipping to a specified page and then scanning that page for a name both take a roughly constant amount of time no matter how many pages the book has.

O(log n): Given a person’s name, find their phone number. The naive way to do this would be start on the first page and keep flipping pages until we reach the person’s name, which would be an O(n) (linear-time) operation. But since phone books are alphabetical, we can do better by performing a binary search: open a page about halfway through the book and determine which half of the book the person’s name would appear in. Now open a page in the middle of that half and do the same thing. Keep repeating until you find the person’s name.

The maximum time you’d take with this method increases only logarithmically with the number of pages. Or to put it another way, as the input increases exponentially, the time increases only linearly, so if the book had 10 times as many pages it would take you only twice as long to find a person’s number.

O(n): Given a person’s phone number, find their name. This is a linear-time operation as it requires you to scan every single page in the book.

O(n log n): Fix a defective phone book that has all its pages inserted in a random order. Take the first page and put it into a new, empty phone book. Take the second page and place it in the new book at the correct spot. Repeat for all pages, using binary search to find the correct spot for each. Since searching for the right spot for each page takes log(n) time, and we need to do this for n pages, the complexity is O(n.log n).