Big O graph comparisons show how an algorithm’s work grows as the input size, n, increases. The most useful order is O(1), O(log n), O(n), O(n log n), O(n²), O(2ⁿ), and O(n!). Curves that look similar at small inputs separate sharply at larger ones.

Big O describes growth, not exact wall-clock time. Hardware, implementation, constants, and input patterns affect measured time, while Big O helps compare how algorithms scale.

Big O graph: How growth rates diverge

This growth-rate chart orders common complexity classes from slowest-growing to fastest-growing:

1. O(1), constant: The work stays roughly the same regardless of n, such as reading an array item by index.
2. O(log n), logarithmic: Each step removes a fraction of the remaining input. Binary search is the standard example.
3. O(n), linear: Work increases in direct proportion to the input, such as scanning every item once.
4. O(n log n), linearithmic: Common in efficient comparison sorting, including merge sort and average-case quicksort.
5. O(n²), quadratic: Two input-sized loops can compare many pairs, as in basic comparison sorts.
6. O(2ⁿ), exponential: Each added input item can double the work, often appearing in exhaustive subset searches.
7. O(n!), factorial: Work grows by trying every permutation, making it impractical quickly.

Big O time complexity from constant to factorial

Concrete scale examples make the divergence easier to judge. At n = 1,000, a linear algorithm performs roughly 1,000 units of work, while a quadratic one can reach about 1,000,000. At n = 1,000,000, O(n) is about 1,000,000 units and O(n²) is about 1,000,000,000,000.

• O(1): About 1 operation remains about 1 operation at every input size.
• O(log n): Binary search needs about 20 halvings for 1,000,000 items because log₂(1,000,000) is close to 20.
• O(n log n): At 1,000,000 items, a rough comparison count is 1,000,000 × 20, before constants and lower-order work.
• O(2ⁿ): At n = 20, there are 1,048,576 possible branches; at 40, there are more than 1 trillion.
• O(n!): 10! equals 3,628,800 arrangements, while 13! exceeds 6 billion.

These are operation-count intuitions, not timing promises. A highly optimized O(n²) routine can beat an O(n log n) routine for a small input, but the growth-rate advantage usually dominates as n expands.

Big O cheat sheet for sorting algorithms

Use this Big O sorting reference to compare the usual best, average, and worst runtimes. Auxiliary space excludes the input array itself.

• Bubble sort: Best O(n) with early-exit detection; average O(n²); worst O(n²); auxiliary space O(1).
• Insertion sort: Best O(n) on an already sorted or nearly sorted list; average O(n²); worst O(n²); auxiliary space O(1).
• Selection sort: Best, average, and worst O(n²); auxiliary space O(1).
• Merge sort: Best, average, and worst O(n log n); auxiliary space O(n) for the usual array implementation.
• Quicksort: Best O(n log n); average O(n log n); worst O(n²) with poor pivot choices; auxiliary space averages O(log n) for the recursion stack and can reach O(n).
• Heap sort: Best, average, and worst O(n log n); auxiliary space O(1).
• Counting sort: Best, average, and worst O(n + k), where k is the value range; auxiliary space O(n + k).

How to read Big O runtime in best, average, and worst cases

Big O runtime labels describe how an algorithm behaves under a selected input condition. Best case is the most favorable arrangement, average case represents typical assumptions, and worst case is the slowest permitted arrangement.

For example, insertion sort is O(n) when data is already ordered because each item moves little, but O(n²) when data is reverse-ordered. Quicksort is usually O(n log n), yet an unfavorable pivot sequence can produce O(n²). Merge sort gives the most consistent comparison-sort bound—O(n log n) in all three cases—but uses extra memory. For nearly sorted, small inputs, insertion sort’s low overhead can be preferable; for predictable large-input performance, merge sort or heap sort offers a stronger worst-case guarantee.