C Big-O Notation

Big-O notation is a way of describing how the running time (or memory use) of an algorithm grows as its input size grows. It doesn’t measure exact seconds or bytes — it measures the shape of growth, so you can compare two algorithms without running them on specific hardware. In C, where you often write the low-level loops yourself, understanding Big-O is essential: it explains why a search over a million records can be instant or agonizingly slow depending on how you wrote the code.

Overview / How it works

Big-O notation answers one question: as the input size n grows very large, how does the number of operations (or memory) grow? It deliberately ignores constant factors and lower-order terms, because those depend on the specific machine, compiler, and optimization level — details that don’t matter once n gets large enough.

When you analyze a C function, you count the operations that scale with input size: loop iterations, comparisons, recursive calls, array accesses. A single for loop that runs n times is O(n). Two nested loops, each running n times, is O(n2) i.e. O(n*n). A loop that cuts the problem in half each time (like binary search) is O(log n).

Internally, what actually costs time in a C program is CPU instructions: comparisons, arithmetic, memory loads/stores, and function call overhead (stack frame setup). Big-O treats all of these as roughly constant-time “steps” and counts how many steps happen as a function of n. It does not care whether one step takes 2 nanoseconds or 20 — only how the count of steps scales. This is why two algorithms with the same Big-O can still have very different real-world speed (one might do more work per step), but as n grows without bound, the algorithm with the better Big-O class always wins.

Big-O is technically an upper bound (worst case, or “no worse than”), but in everyday use programmers say “Big-O” to mean the typical growth rate of an algorithm. Related notations you may see are Ω (Omega, best case / lower bound) and Θ (Theta, tight bound when best and worst case match), but Big-O is by far the most commonly used in day-to-day discussion.

Common complexity classes

Notation Name Example
O(1) Constant Accessing arr[i], pushing to a stack
O(log n) Logarithmic Binary search on a sorted array
O(n) Linear Linear search, one pass over an array
O(n log n) Linearithmic Merge sort, quicksort (average case)
O(n2) Quadratic Bubble sort, insertion sort, nested loops over the same array
O(2n) Exponential Naive recursive Fibonacci, brute-force subset enumeration

Syntax

Big-O is written mathematically, not as C syntax, but the convention is consistent:

O(f(n))
  • O — stands for “Order of”; it introduces the growth-rate bound.
  • f(n) — a function of the input size n, such as n, n2, log n, or 1 (constant).
  • n — the size of the input: array length, number of nodes, string length, etc.

To find the Big-O of a piece of C code, follow these rules of thumb:

  • A simple statement (assignment, comparison, arithmetic) is O(1).
  • A loop that runs n times, containing O(1) work per iteration, is O(n).
  • Nested loops multiply: a loop inside a loop, each running n times, is O(n) * O(n) = O(n2).
  • Sequential (non-nested) blocks add, and you keep only the largest term: O(n) + O(n2) simplifies to O(n2).
  • Constants are dropped: O(2n) is written O(n); O(n + 5) is written O(n).
  • A loop that halves the remaining range each iteration is O(log n).

Examples

Example 1: O(n) — Linear Search

Linear search checks every element one by one until it finds the target (or reaches the end). In the worst case it inspects all n elements, so it is O(n).

#include <stdio.h>

int linearSearch(int arr[], int n, int target, long *comparisons) {
    for (int i = 0; i < n; i++) {
        (*comparisons)++;
        if (arr[i] == target) {
            return i;
        }
    }
    return -1;
}

int main(void) {
    int arr[] = {4, 2, 9, 7, 5, 1, 8, 3, 6, 10};
    int n = sizeof(arr) / sizeof(arr[0]);
    long comparisons = 0;

    int index = linearSearch(arr, n, 8, &comparisons);

    printf("Found 8 at index %d\n", index);
    printf("Comparisons made: %ld\n", comparisons);

    return 0;
}

Output:

Found 8 at index 6
Comparisons made: 7

The function walks the array from the start and stops as soon as it finds 8, which happens to sit at index 6. In the worst case (target not present, or at the last position), it would perform exactly n comparisons — that linear relationship between input size and work is what makes this O(n).

Example 2: O(log n) — Binary Search

Binary search only works on a sorted array, but in exchange it eliminates half the remaining elements on every comparison, giving logarithmic growth.

#include <stdio.h>

int binarySearch(int arr[], int n, int target, long *comparisons) {
    int low = 0, high = n - 1;
    while (low <= high) {
        (*comparisons)++;
        int mid = low + (high - low) / 2;
        if (arr[mid] == target) {
            return mid;
        } else if (arr[mid] < target) {
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }
    return -1;
}

int main(void) {
    int arr[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16};
    int n = sizeof(arr) / sizeof(arr[0]);
    long comparisons = 0;

    int index = binarySearch(arr, n, 13, &comparisons);

    printf("Found 13 at index %d\n", index);
    printf("Comparisons made: %ld\n", comparisons);

    return 0;
}

Output:

Found 13 at index 12
Comparisons made: 4

With 16 elements, linear search could take up to 16 comparisons, but binary search finds the target in just 4 — because log2(16) = 4. Every failed guess throws away half of the remaining candidates, so doubling the array size only adds one extra comparison, not a whole new pass.

Example 3: O(n2) — Nested Loops (Bubble Sort)

Bubble sort compares adjacent elements and swaps them if out of order, using two nested loops. The inner loop’s work depends on the outer loop’s position, but the total comparisons still scale with n2.

#include <stdio.h>

long bubbleSortComparisons(int n) {
    int arr[100];
    for (int i = 0; i < n; i++) {
        arr[i] = n - i;
    }

    long comparisons = 0;
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - i - 1; j++) {
            comparisons++;
            if (arr[j] > arr[j + 1]) {
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
    return comparisons;
}

int main(void) {
    int sizes[] = {10, 20, 40, 80};
    int count = sizeof(sizes) / sizeof(sizes[0]);

    for (int i = 0; i < count; i++) {
        int n = sizes[i];
        long comparisons = bubbleSortComparisons(n);
        printf("n = %3d -> comparisons = %ld\n", n, comparisons);
    }

    return 0;
}

Output:

n =  10 -> comparisons = 45
n =  20 -> comparisons = 190
n =  40 -> comparisons = 780
n =  80 -> comparisons = 3160

Notice the pattern: each time n doubles, the comparison count roughly quadruples (45 → 190 → 780 → 3160, each about 4× the previous). That 4× growth for a 2× input increase is the signature of O(n2) — because (2n)2 = 4n2. For comparison, the linear search in Example 1 would only double its work when n doubles.

How it works step by step / Under the hood

  • Step 1 — identify the input size n. This is usually the array length, string length, or number of nodes/elements the algorithm processes.
  • Step 2 — find the loops and recursive calls. Each loop that depends on n contributes a factor to the total operation count.
  • Step 3 — multiply nested loops, add sequential blocks. Two loops nested inside each other multiply their costs; two loops that run one after another add their costs (and you keep only the dominant term).
  • Step 4 — drop constants and lower-order terms. 3n + 20 becomes O(n); n2 + 100n becomes O(n2) because as n grows, the n2 term dominates.
  • Step 5 — consider the worst case (unless stated otherwise). Big-O usually describes the worst-case scenario — the target is the last element checked, the array is already reverse-sorted, and so on.

At the machine level, every iteration of a loop translates into a handful of CPU instructions: a comparison against a loop bound, a conditional jump, the loop body’s own instructions, and an increment. The compiler and CPU pipeline these instructions extremely efficiently, but they cannot change the fundamental count of iterations — that count is exactly what Big-O captures. This is why an O(n2) algorithm on a fast machine can still be slower than an O(n log n) algorithm on a slow machine, once n is large enough: the gap in iteration count eventually swamps any difference in raw clock speed.

Common Mistakes

Mistake 1: Counting lines of code instead of iterations. Beginners often assume more lines means worse Big-O. A single for loop with 20 statements inside is still O(n), not “worse” than a loop with 2 statements — the constant work per iteration doesn’t change the growth class.

/* Still O(n): the number of statements per iteration is a constant,
   it does not depend on n, so it doesn't change the Big-O class. */
for (int i = 0; i < n; i++) {
    /* 20 unrelated O(1) statements here */
}

Mistake 2: Missing hidden loops inside library or helper functions. Calling strlen() inside a loop silently adds an extra O(n) pass every iteration, because strlen itself scans the whole string.

/* Wrong: this is O(n^2), not O(n) -- strlen(s) rescans the
   string on every single iteration of the outer loop. */
for (int i = 0; i < strlen(s); i++) {
    /* process s[i] */
}

The fix is to compute the length once, outside the loop, so the scan happens a single time:

/* Correct: O(n) -- length is computed once before the loop. */
int len = strlen(s);
for (int i = 0; i < len; i++) {
    /* process s[i] */
}

Mistake 3: Assuming binary search works on unsorted data. Binary search’s O(log n) guarantee depends entirely on the array being sorted; running it on unsorted data gives wrong results, not just a slower search.

Best Practices

  • Analyze the worst case first, then check whether the average or best case matters for your use.
  • Watch for function calls inside loops (strlen, strcmp, recursive helpers) — they can hide an extra factor of n.
  • Prefer O(log n) or O(n log n) algorithms (binary search, merge sort, quicksort) over O(n2) ones once your data sets grow into the thousands or millions.
  • Remember that Big-O ignores constants, so for very small n a “worse” algorithm can still run faster in practice — measure with real data when performance actually matters.
  • Keep sorted data sorted if you plan to binary-search it repeatedly; sorting itself costs O(n log n), so it only pays off across multiple searches.
  • Track memory growth too (space complexity) — an algorithm that allocates an n by n array uses O(n2) memory even if its running time is faster.

Practice Exercises

  • Exercise 1: Write a C function that finds the maximum value in an array of n integers using a single loop. State its Big-O and explain why.
  • Exercise 2: Given two nested loops where the outer loop runs n times and the inner loop always runs exactly 5 times (not depending on n), what is the Big-O of the combined loops? Justify your answer.
  • Exercise 3: Modify the bubble sort program from Example 3 to also count the number of swaps (not just comparisons) for an array that is already sorted in ascending order. What do you expect the swap count to be, and why does the comparison count not change?

Summary

  • Big-O notation describes how an algorithm’s running time or memory grows as the input size n increases, ignoring constants and hardware-specific details.
  • Common classes, from best to worst for large n, are O(1), O(log n), O(n), O(n log n), O(n2), and O(2n).
  • Nested loops over the same input typically multiply to give O(n2) or worse; sequential blocks add, keeping only the dominant term.
  • Binary search’s O(log n) comes from halving the search range each step, but it requires sorted data.
  • Watch for hidden costs, like calling strlen() inside a loop, which silently turns an O(n) algorithm into O(n2).
  • Big-O is a tool for reasoning about scalability, not a replacement for measuring real performance on real data.