Complexity Classes Cheat Sheet

A complexity cheat sheet is a quick reference to the common Big-O classes ordered from fastest- to slowest-growing, so you can instantly judge whether an algorithm scales. This page collects them in one table, shows how fast each grows for real input sizes, and illustrates two of them — O(n) and O(log n) — side by side in code.

The classes, best to worst

How fast they actually grow

Numbers make the difference visceral. Approximate operation counts:

n          O(log n)   O(n)       O(n log n)   O(n^2)        O(2^n)
10         ~3         10         ~33          100           1,024
100        ~7         100        ~664         10,000        ~1.3e30
1,000      ~10        1,000      ~9,966       1,000,000     astronomical
1,000,000  ~20        1,000,000  ~2e7         1e12          impossible

The lesson: O(n²) is fine at n = 1,000 (a million ops) but hopeless at n = 1,000,000 (a trillion ops). O(2ⁿ) and O(n!) are usable only for tiny n (≈ 20 and ≈ 11). Use these thresholds to pick a target complexity from a problem’s constraints.

For beginners: As a rough rule for a 1-second limit, you can do about 10^8 simple operations. So if n ≤ 10^5, aim for O(n log n) or better; if n ≤ 10^3, O(n²) is acceptable; if n ≤ 20, even O(2ⁿ) may pass.

O(n) vs O(log n), side by side

The clearest contrast: searching a value in a sorted array. Linear search checks every element — O(n). Binary search halves the range each step — O(log n). Both return the index or -1.

#include <vector>
using namespace std;

int linearSearch(const vector<int>& a, int target) { // O(n)
    for (int i = 0; i < (int)a.size(); i++)
        if (a[i] == target) return i;
    return -1;
}

int binarySearch(const vector<int>& a, int target) { // O(log n), a must be sorted
    int lo = 0, hi = (int)a.size() - 1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        if (a[mid] == target) return mid;
        if (a[mid] < target) lo = mid + 1;
        else hi = mid - 1;
    }
    return -1;
}

int linearSearch(int[] a, int target) { // O(n)
    for (int i = 0; i < a.length; i++)
        if (a[i] == target) return i;
    return -1;
}

int binarySearch(int[] a, int target) { // O(log n), a must be sorted
    int lo = 0, hi = a.length - 1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        if (a[mid] == target) return mid;
        if (a[mid] < target) lo = mid + 1;
        else hi = mid - 1;
    }
    return -1;
}

function linearSearch(a, target) { // O(n)
  for (let i = 0; i < a.length; i++)
    if (a[i] === target) return i;
  return -1;
}

function binarySearch(a, target) { // O(log n), a must be sorted
  let lo = 0, hi = a.length - 1;
  while (lo <= hi) {
    const mid = lo + Math.floor((hi - lo) / 2);
    if (a[mid] === target) return mid;
    if (a[mid] < target) lo = mid + 1;
    else hi = mid - 1;
  }
  return -1;
}

def linear_search(a, target):  # O(n)
    for i, x in enumerate(a):
        if x == target:
            return i
    return -1

def binary_search(a, target):  # O(log n), a must be sorted
    lo, hi = 0, len(a) - 1
    while lo <= hi:
        mid = lo + (hi - lo) // 2
        if a[mid] == target:
            return mid
        if a[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1

On a million-element array, linear search may touch a million elements; binary search needs at most ~20 comparisons. That gap is why sorted data plus binary search is one of DSA’s most powerful combinations.

Going deeper: Binary search’s O(log n) assumes the input is already sorted. If you must sort first, that’s O(n log n) up front — worth it only when you search many times. Always count the cost of the precondition, not just the search.

Reading complexity off code fast

• One pass over the input → O(n).
• Halving or doubling a counter → O(log n).
• Sort, then a single pass → O(n log n).
• Nested loops over the same input → O(n²).
• Trying all subsets → O(2ⁿ); all orderings → O(n!).

Next steps

To derive these rather than memorize them, read analyzing loops and analyzing recursion. Then lock it in with the complexity exercises and their solutions.