ALGORITHMSChapter 10 · Algorithms and Problem Solving

How fast is my code?

Big O describes how the amount of work grows as the input grows. Reading a list item by index is O(1): one step no matter how long the list is. A single loop over n items is O(n). A loop inside a loop over the same items is O(n^2): double the input and the work quadruples. Counting the steps yourself is the best way to build a feel for it.

Worked example

How it reads

Doubling n doubles the linear count: O(n)
Doubling n quadruples the nested count: O(n^2)
Checking x in some_set is O(1) on average; x in some_list is O(n)

Cloud tip: Ask "what happens if the input is 1,000 times bigger?" An O(n^2) answer that is fine for 100 items can take hours for 100,000.

Go deeper: The common growth rates

From fastest to slowest:

O(1): constant, like indexing a list or a dict lookup
O(log n): halving each step, like binary search
O(n): one pass, like summing a list
O(n log n): good sorting algorithms, like sorted()
O(n^2): comparing every pair
O(2^n): trying every subset, only workable for tiny inputs