Common Complexity Classes

Learning Objectives

By the end of this section, you will be able to:

1. Identify and describe the major complexity classes from O(1) to O(n!)
2. Recognize code patterns that produce each complexity class
3. Understand the practical implications of each class for real-world systems
4. Make informed decisions about algorithm selection based on input size and complexity
5. Calculate feasibility thresholds for different complexity classes

Why This Matters: When you see code, you should instantly recognize its complexity class like a musician reads sheet music. This skill separates engineers who build scalable systems from those who create systems that collapse under load. Every technical interview will test this, and every production system depends on it.

The Complexity Hierarchy

Complexity classes form a hierarchy from fastest to slowest growing. Understanding this hierarchy is fundamental to algorithm analysis and selection.

Let's visualize how dramatically these differ. For n = 1,000,000 (a million elements, quite modest by modern standards):

O(1): Constant Time

Constant time operations complete in the same amount of time regardless of input size. The algorithm does a fixed number of operations—whether working with 10 elements or 10 billion.

The Defining Characteristic

The runtime does not depend on n. There are no loops that scale with input, no recursion that deepens with input, and no data structure traversals.

arr[500] takes the same time as arr[0]

Finding a key in a dictionary with 1 or 1 million entries takes the same average time

1// O(1) Examples in C
2
3// 1. Direct array access
4int get_element(int arr[], int i) {
5    return arr[i];  // One memory operation
6}
7
8// 2. Hash table lookup (average case)
9int get_from_hash(HashMap* map, int key) {
10    int bucket = hash(key) % map->size;  // One hash + one modulo
11    return map->buckets[bucket]->value;  // Direct access
12}
13
14// 3. Stack push/pop
15void push(Stack* s, int value) {
16    s->data[++s->top] = value;  // Increment and assign
17}
18
19// 4. Simple arithmetic
20int compute(int a, int b, int c) {
21    return a * b + c / 2 - 7;  // Fixed operations
22}

Common O(1) Operations

O(log n): Logarithmic Time

Logarithmic algorithms are extraordinarily efficient. They achieve this by eliminating a constant fraction of possibilities with each step, typically half.

The Core Insight

If you can eliminate half the remaining candidates at each step, you reach an answer in at most $\log_2 n$ steps. This is because:

Starting with n elements and halving k times until 1 remains requires exactly $\log_2 n$ halvings.

1000 elements → 500 → 250 → 125 → ... → 1 (about 10 steps)

1// O(log n) Binary Search in C
2
3int binary_search(int arr[], int n, int target) {
4    int left = 0, right = n - 1;
5
6    while (left <= right) {
7        int mid = left + (right - left) / 2;  // Avoid overflow
8
9        if (arr[mid] == target)
10            return mid;       // Found!
11        else if (arr[mid] < target)
12            left = mid + 1;   // Eliminate left half
13        else
14            right = mid - 1;  // Eliminate right half
15    }
16    return -1;  // Not found
17}
18
19// Time complexity analysis:
20// - Each iteration halves the search space
21// - Starting with n, after k iterations: n/2^k elements remain
22// - Loop ends when n/2^k = 1, i.e., k = log₂(n)
23// - Total: O(log n)

The Power of Logarithmic Growth

Logarithms grow incredibly slowly. This table shows why O(log n) algorithms can handle massive inputs:

Common O(log n) Operations

O(n): Linear Time

Linear time algorithms process each element of the input exactly once (or a constant number of times). If you double the input, you double the work.

When Is Linear Time Optimal?

Many problems have an $\Omega(n)$ lower bound—you must examine every element at least once:

• Finding the maximum in an unsorted array (must check all elements)
• Computing the sum of elements (must see every element)
• Checking if an element exists in an unsorted collection
• Validating that all elements satisfy a property

For these problems, an O(n) algorithm is optimal—you cannot do better.

For n = 1,000,000: exactly 1,000,000 iterations

1// O(n) Linear Time Examples in C
2
3// Finding maximum and computing sum
4void analyze_array(int arr[], int n, int* max_out, int* sum_out) {
5    int max_val = arr[0];
6    int sum = 0;
7
8    for (int i = 0; i < n; i++) {
9        if (arr[i] > max_val)
10            max_val = arr[i];
11        sum += arr[i];
12    }
13
14    *max_out = max_val;
15    *sum_out = sum;
16}
17
18// Linear search
19int linear_search(int arr[], int n, int target) {
20    for (int i = 0; i < n; i++) {
21        if (arr[i] == target)
22            return i;
23    }
24    return -1;
25}
26
27// Counting occurrences
28int count_value(int arr[], int n, int value) {
29    int count = 0;
30    for (int i = 0; i < n; i++) {
31        if (arr[i] == value)
32            count++;
33    }
34    return count;
35}

Linear Time in Practice

O(n) is the sweet spot for many algorithms. It scales well and is often optimal:

O(n log n): Linearithmic Time

Linearithmic (or "n log n") is the complexity of efficient divide-and-conquer algorithms. It's slightly worse than linear but dramatically better than quadratic.

The Sorting Lower Bound

A fundamental result in computer science: any comparison-based sorting algorithm must make at least $\Omega(n \log n)$ comparisons in the worst case. This means:

• Merge sort at O(n log n) is optimal for comparison sorting
• Heap sort and quick sort (average case) achieve this bound
• You cannot sort faster using only comparisons

The Divide-and-Conquer Pattern

O(n log n) typically arises from this pattern:

1. Divide: Split the problem into two subproblems of size n/2
2. Conquer: Recursively solve each subproblem
3. Combine: Merge the results in O(n) time

This gives the recurrence $T(n) = 2T(n/2) + O(n)$, which solves to $T(n) = O(n \log n)$.

1// O(n log n) Merge Sort
2
3void merge(int arr[], int left, int mid, int right) {
4    // O(n) merge step
5    int n1 = mid - left + 1;
6    int n2 = right - mid;
7
8    int L[n1], R[n2];  // Temporary arrays
9
10    for (int i = 0; i < n1; i++) L[i] = arr[left + i];
11    for (int j = 0; j < n2; j++) R[j] = arr[mid + 1 + j];
12
13    int i = 0, j = 0, k = left;
14    while (i < n1 && j < n2) {
15        if (L[i] <= R[j])
16            arr[k++] = L[i++];
17        else
18            arr[k++] = R[j++];
19    }
20    while (i < n1) arr[k++] = L[i++];
21    while (j < n2) arr[k++] = R[j++];
22}
23
24void merge_sort(int arr[], int left, int right) {
25    if (left < right) {
26        int mid = left + (right - left) / 2;
27
28        merge_sort(arr, left, mid);       // T(n/2)
29        merge_sort(arr, mid + 1, right);  // T(n/2)
30        merge(arr, left, mid, right);      // O(n)
31    }
32    // Recurrence: T(n) = 2T(n/2) + O(n)
33    // Solution: T(n) = O(n log n)
34}

Where O(n log n) Appears

O(n\u00B2), O(n\u00B3): Polynomial Time

Polynomial time algorithms (O(n^k) for some constant k) are considered "tractable" in complexity theory, but in practice, high-degree polynomials quickly become impractical.

O(n\u00B2): Quadratic Time

Quadratic time typically arises from nested loops where both iterate over the input. Common patterns include:

• Comparing every element with every other element
• Simple sorting algorithms (bubble, selection, insertion)
• Finding all pairs that satisfy some condition
• Dynamic programming with two dimensions of size n

For n = 1000: 1,000,000 iterations. For n = 10,000: 100,000,000 iterations!

1// O(n²) Quadratic Time Examples
2
3// 1. Checking all pairs - Classic O(n²)
4bool has_pair_with_sum(int arr[], int n, int target) {
5    for (int i = 0; i < n; i++) {
6        for (int j = i + 1; j < n; j++) {
7            if (arr[i] + arr[j] == target)
8                return true;
9        }
10    }
11    return false;
12}
13
14// 2. Triangular loop - Still O(n²)!
15void print_pairs_once(int arr[], int n) {
16    for (int i = 0; i < n; i++) {
17        for (int j = i + 1; j < n; j++) {  // Starts at i+1
18            printf("(%d, %d)\n", arr[i], arr[j]);
19        }
20    }
21    // Iterations: (n-1) + (n-2) + ... + 1 = n(n-1)/2 = O(n²)
22}
23
24// 3. Bubble Sort - The classic O(n²) sort
25void bubble_sort(int arr[], int n) {
26    for (int i = 0; i < n - 1; i++) {
27        for (int j = 0; j < n - i - 1; j++) {
28            if (arr[j] > arr[j + 1]) {
29                int temp = arr[j];
30                arr[j] = arr[j + 1];
31                arr[j + 1] = temp;
32            }
33        }
34    }
35}

O(n\u00B3): Cubic Time

Cubic time typically comes from three nested loops or matrix operations:

1// O(n³) Cubic Time Examples
2
3// 1. Naive matrix multiplication
4void matrix_multiply(int A[][N], int B[][N], int C[][N], int n) {
5    for (int i = 0; i < n; i++) {           // n iterations
6        for (int j = 0; j < n; j++) {       // n iterations
7            C[i][j] = 0;
8            for (int k = 0; k < n; k++) {   // n iterations
9                C[i][j] += A[i][k] * B[k][j];
10            }
11        }
12    }
13    // Total: n × n × n = O(n³)
14}
15
16// 2. Floyd-Warshall all-pairs shortest paths
17void floyd_warshall(int dist[][V], int V) {
18    for (int k = 0; k < V; k++) {
19        for (int i = 0; i < V; i++) {
20            for (int j = 0; j < V; j++) {
21                if (dist[i][k] + dist[k][j] < dist[i][j])
22                    dist[i][j] = dist[i][k] + dist[k][j];
23            }
24        }
25    }
26}

O(n\u00B3) becomes impractical quickly. For n = 1,000, you have 1 billion operations (about 1 second). For n = 10,000, that's a trillion operations (about 16 minutes).

O(2\u207F), O(n!): Exponential and Factorial

These complexities represent the boundary between solvable and unsolvable problems at scale. They grow so fast that even small increases in n make problems intractable.

O(2\u207F): Exponential Time

Exponential algorithms typically enumerate all subsets or make binary choices at each step:

1// O(2^n) Exponential Time Examples
2
3// 1. Generate all subsets (power set)
4void generate_subsets(int arr[], int n) {
5    // There are 2^n possible subsets
6    for (int mask = 0; mask < (1 << n); mask++) {
7        printf("{ ");
8        for (int i = 0; i < n; i++) {
9            if (mask & (1 << i))
10                printf("%d ", arr[i]);
11        }
12        printf("}\n");
13    }
14}
15
16// 2. Naive Fibonacci (recursive)
17int fib_naive(int n) {
18    if (n <= 1) return n;
19    return fib_naive(n - 1) + fib_naive(n - 2);
20    // Each call makes 2 calls, creating ~2^n total calls
21    // (Actually O(φ^n) where φ ≈ 1.618)
22}
23
24// 3. Subset sum (brute force)
25bool subset_sum_exists(int arr[], int n, int target) {
26    for (int mask = 0; mask < (1 << n); mask++) {
27        int sum = 0;
28        for (int i = 0; i < n; i++) {
29            if (mask & (1 << i))
30                sum += arr[i];
31        }
32        if (sum == target) return true;
33    }
34    return false;
35}

O(n!): Factorial Time

Factorial is even worse than exponential. It grows so fast that even n = 20 is essentially unsolvable:

1// O(n!) Factorial Time Examples
2
3// Generate all permutations
4void permute(char str[], int l, int r) {
5    if (l == r) {
6        printf("%s\n", str);
7    } else {
8        for (int i = l; i <= r; i++) {
9            swap(&str[l], &str[i]);
10            permute(str, l + 1, r);
11            swap(&str[l], &str[i]);  // Backtrack
12        }
13    }
14    // For string of length n: prints n! permutations
15}
16
17// Traveling Salesman Problem (brute force)
18int tsp_brute_force(int graph[][N], int n) {
19    int vertices[n - 1];
20    for (int i = 0; i < n - 1; i++) vertices[i] = i + 1;
21
22    int min_cost = INT_MAX;
23
24    // Try all permutations of vertices 1 to n-1
25    do {
26        int cost = graph[0][vertices[0]];
27        for (int i = 0; i < n - 2; i++)
28            cost += graph[vertices[i]][vertices[i + 1]];
29        cost += graph[vertices[n - 2]][0];
30
31        if (cost < min_cost) min_cost = cost;
32    } while (next_permutation(vertices, n - 1));
33
34    return min_cost;
35    // Complexity: O((n-1)!) ≈ O(n!)
36}

Interactive: Complexity Class Explorer

Use this interactive tool to explore all complexity classes. Adjust the input size, select different classes, and watch how operations scale. Pay attention to when each class becomes impractical.

Here's another view comparing growth rates visually. Toggle different complexity classes to see how they diverge:

Practical Thresholds

Given a time budget (e.g., "must complete in 1 second") and assuming 10&sup9; operations per second, here are approximate maximum input sizes for each complexity:

Rule of Thumb for Interviews

When given a time constraint in a coding interview, use these guidelines:

Recognizing Complexity in Code

With practice, you should instantly recognize the complexity of code patterns. Here's a cheat sheet:

Pattern Recognition Guide

Quick Test: What's the Complexity?

1// What is the complexity of each function?
2
3// Function A
4int func_a(int n) {
5    int sum = 0;
6    for (int i = 1; i <= n; i *= 2)  // How many iterations?
7        sum += i;
8    return sum;
9}
10
11// Function B
12void func_b(int n) {
13    for (int i = 0; i < n; i++)       // n iterations
14        for (int j = 0; j < 100; j++) // 100 iterations (constant!)
15            printf("*");
16}
17
18// Function C
19int func_c(int n) {
20    if (n <= 1) return n;
21    return func_c(n/2) + func_c(n/2);  // Two recursive calls
22}
23
24// Function D
25void func_d(int n) {
26    for (int i = 0; i < n; i++)
27        for (int j = i; j < n; j++)
28            printf("%d %d\n", i, j);
29}

Summary

You now have a comprehensive understanding of the complexity class hierarchy:

Key Takeaways

1. The hierarchy matters: O(n log n) is dramatically better than O(n\u00B2) at scale
2. Polynomial vs exponential: O(n\u00B3) is slow but tractable; O(2\u207F) is intractable for large n
3. Recognize patterns: Nested loops usually mean O(n\u00B2), halving means O(log n)
4. Match complexity to input size: Know the practical limits for your time budget
5. Always ask: Can I do better? If O(n\u00B2) exists, often O(n log n) does too

Exercises

Conceptual Questions

1. Why is O(n log n) considered the "gold standard" for sorting? What prevents us from sorting faster using comparisons?
2. Explain why O(1000n) = O(n) but O(n\u00B2) \u2260 O(n), even though 1000 > n for small n.
3. A problem has input size n = 50. Your boss says an O(2\u207F) solution is "fine since n is small." Is this reasonable? Calculate the operations.
4. Why does the loop "for (i = n; i > 0; i /= 2)" run O(log n) times, not O(n/2) times?

Complexity Analysis

1. Determine the complexity:
   📄exercise1.c

   Copy

   1for (int i = 0; i < n; i++)
   2    for (int j = 0; j < n; j++)
   3        for (int k = 0; k < n; k++)
   4            if (arr[i] + arr[j] + arr[k] == target)
   5                return true;
2. Determine the complexity:
   📄exercise2.c

   Copy

   1for (int i = 1; i < n; i *= 2)
   2    for (int j = 0; j < n; j++)
   3        sum += arr[j];
3. Determine the complexity:
   📄exercise3.c

   Copy

   1int i = n;
   2while (i > 0) {
   3    for (int j = 0; j < i; j++)
   4        printf("*");
   5    i /= 2;
   6}
4. A function has the recurrence T(n) = T(n/2) + n. What is its complexity? (Hint: expand the recurrence)

Design Questions

1. You need to find if any two numbers in an unsorted array sum to a target value. The naive approach is O(n\u00B2). Can you achieve O(n)? (Hint: hash table)
2. Given a sorted array, finding a single element is O(log n). How would you modify binary search to count all occurrences of an element? What's the complexity?

In the next section, we'll explore Space Complexity—analyzing not just the time an algorithm takes, but the memory it consumes. You'll learn that sometimes trading time for space (or vice versa) is the key to solving a problem efficiently.