Big-O Notation

On this page

The Idea
Build It
Know It
Break It
Use It

Quick reference

O(1) — constant	O(1)
O(log n) — logarithmic	O(log n)
O(n) — linear	O(n)
O(n log n) — linearithmic	O(n log n)
O(n²) — quadratic	O(n²)
O(2ⁿ) — exponential	O(2ⁿ)
O(n!) — factorial	O(n!)

The Idea

Two programs can solve the same problem. Both programs can be correct. But the two programs can be very different in practice. One program gives a result immediately. The other program stops your computer when the input becomes large. Big-O is the language for this difference. Big-O answers one question. When the input size N becomes larger, how does the quantity of work become larger? Big-O does not measure the time in milliseconds on your machine. That time changes with the CPU speed, the language, and the other programs that run. Big-O describes the shape of the growth. This shape is true on all machines, in all languages, and at all times.

This is why we remove the machine data and use N. A loop that touches each element one time does approximately N units of work. This is true if N is 10 or 10 million. We call this O(n). A loop inside another loop does approximately N multiplied by N units of work. We call this O(n²). We remove the exact constants. For example, we do not keep the difference between 2N operations and 5N operations. The constants do not change the shape of the growth. The shape shows if your program can process a large input.

Three cases are important. The best case is the most agreeable input. The best case is usually not useful for your plans. The worst case is the input that makes your algorithm do the most work. You must design for the worst case. The average case is the usual result for realistic inputs. The average case is useful when the worst case is rare and expensive to prevent. A hash map that manages collisions is an example. When people say that an algorithm is O(n) with no more data, they usually mean the worst case. You must also assume the worst case.

Big-O shows the trend when N becomes large. Big-O does not show the exact number of operations. O(n) means that the work increases at the same rate as the input size. O(n) does not tell you which algorithm is faster between two O(n) algorithms on a specific input.

Build It

How to find the class

// The method: read the code. Count how the "work" increases with N. Give the class a name.
// Ask one question for each loop or structure: "Does this range depend on N? How?"
//   - a fixed number of steps, for all sizes of N              -> O(1)
//   - one pass over N items                                    -> O(n)
//   - a loop inside a loop, each over N items                  -> O(n^2)
//   - a loop that divides the remaining work by two each step  -> O(log n)
// Multiply the nested or sequential costs. Then keep only the term that increases most quickly.

constant time — O(1)

function firstElement(arr):
    return arr[0]        // One lookup. The cost is the same for all sizes of arr.

No loop touches N. The cost does not change when the input becomes larger. Thus the operation is O(1), even if the line is expensive.

single loop — O(n)

function sum(arr):
    total = 0
    for x in arr:          // This loop runs N times.
        total += x          // This line does constant work for each iteration.
    return total

One line does constant work. The line runs one time for each element. N iterations multiplied by O(1) for each iteration gives O(n). This is the basic pattern. Each single pass over the input is O(n).

nested loop — O(n²)

function hasDuplicatePair(arr):
    for i in range(len(arr)):        // This loop runs N times.
        for j in range(len(arr)):    // This loop runs N times for each value of i.
            if i != j and arr[i] == arr[j]:
                return true
    return false

The outer loop runs N times. For each of these times, the inner loop also runs N times. The total work is N multiplied by N, which is O(n²). This is the usual pattern that compares each pair.

halving loop — O(log n)

function binarySearch(sortedArr, target):
    lo, hi = 0, len(sortedArr) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if sortedArr[mid] == target:
            return mid
        elif sortedArr[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1     // Each iteration removes half of the remaining range.
    return -1

The algorithm divides the search space by two at each iteration. It does not decrease the search space by a fixed quantity. To go from N to 1 by division by two takes log₂(N) steps. This makes the algorithm O(log n). O(log n) increases much more slowly than O(n).

Know It

This list shows the classes in sequence, from the least expensive growth to the most expensive growth. The last column is the most important column to memorize. The last column tells you if an approach can process a realistic input size. This is useful during an interview or a code review.

Operation	Time	Space	Why
O(1) — constant	O(1)	—	The cost is the same at n = 10 or n = 1,000,000. Examples are a hash lookup, an array index, and a fixed arithmetic formula.
O(log n) — logarithmic	O(log n)	—	At n = 1,000,000, log₂n is approximately 20. Division of the problem by two at each step finds the answer very quickly. Binary search is the usual example.
O(n) — linear	O(n)	—	The algorithm does one pass over the input. At n = 1,000,000, this is 1,000,000 operations. This is fast. It is usually the best result when you must look at each element.
O(n log n) — linearithmic	O(n log n)	—	At n = 1,000,000, this is approximately 20,000,000 operations. This is still fast. Good sorting algorithms use this class. Examples are merge sort and heap sort.
O(n²) — quadratic	O(n²)	—	At n = 1,000,000, this is one trillion operations. Do not use this class at this size. It is acceptable at n = 100. It is dangerous when the input size is not small. Every-pair comparisons are in this class.
O(2ⁿ) — exponential	O(2ⁿ)	—	At n = 30, this is already more than one billion. At n = 1,000,000, the number is too large to calculate. This class occurs in brute-force approaches that try each subset.
O(n!) — factorial	O(n!)	—	At n = 20, the number is larger than you can enumerate. This class occurs when you try each order or permutation. It is only possible for a very small N.

Break It

Constants are not always unimportant

N is small and has a limit

Big-O removes constants because the constants become unimportant when N becomes large. But sometimes N has a limit. For example, N is a maximum of 20 for a fixed-size board or a small configuration list. Then an O(n²) algorithm with small constants can be faster than an O(n log n) algorithm with large overhead for each step. Big-O describes the trend at a large scale. Big-O does not tell you which code is faster on your actual input.

A loop that becomes smaller is still O(n²)

the range becomes smaller by 1 at each outer iteration

A loop such as "for i in range(n): for j in range(i, n)" looks smaller at each pass. The inner loop runs n times, then n-1 times, then n-2 times. But the total is n + (n-1) + (n-2) + ... + 1, which is equal to n(n+1)/2. This is still a quadratic expression. When you remove the constants and the lower-order terms, n(n+1)/2 is O(n²), not O(n). Big-O measures the total work, not the quantity for each iteration.

Worst case compared to average case

the cost of an operation depends on the data, not only on N

A hash map lookup is O(1) on average. But sometimes each key goes to the same bucket. This can occur with a bad hash function or an adversarial input. Then the lookup becomes O(n) in the worst case, because you must go through a full bucket chain. If you say "O(1)" with no qualifier, you hide this risk. Know which case you claim.

A hidden O(n) inside a loop

the simple operation inside your loop is not O(1)

The code "for i in range(n): result += arr[:i]" looks like one O(n) loop. But a slice or a concatenation of a string or a list is O(k) in the size that you build. Thus the real cost is 1 + 2 + ... + n, which is approximately O(n²), not O(n). Always ask if the line inside your loop is really constant time before you count the loop.

Use It

Two Sum

A brute-force method checks each pair, which is O(n²). A hash map stores each value and its index. The hash map changes the second loop into one lookup, which is O(n).

Easy

Contains Duplicate

A pairwise comparison is O(n²). Put each element into a hash set as you go. Check for membership first. This method is O(n).

Easy

Best Time to Buy and Sell Stock

A check of each pair of buy days and sell days is O(n²). Keep the minimum price that you have seen. This changes the method into one O(n) pass.

Easy

Valid Anagram

To sort both strings and compare them is O(n log n). To count the character frequencies in one pass for each string is O(n).

Easy

Majority Element

To sort the array and find the middle element is O(n log n). To count the occurrences with a hash map is O(n). The Boyer-Moore voting algorithm is also O(n).

Easy

Missing Number

To sort the array and look for the gap is O(n log n). To compare the sum of 0 to n against the actual sum of the array is O(n).

Easy

Move Zeroes

This is a space improvement, not a time improvement. To build a new filtered array uses O(n) extra space. To move the non-zero elements to the left in place uses O(1) space.

Easy

Intersection of Two Arrays

To check each element of one array against each element of the other array is O(n·m). Put one array into a hash set first. Then each lookup is O(1), for a total of O(n+m).

Easy

Single Number

A hash set that counts elements is O(n) time and O(n) space. The XOR of all elements removes all paired values. The XOR method is O(n) time and O(1) space. It has the same time class but better space.

Easy

Squares of a Sorted Array

To square the values and then sort them is O(n log n). To use two indices that start at both ends and move to the middle is O(n).

Easy