C++ Big-O Notation

Big-O notation is a way of describing how the running time (or memory usage) of an algorithm grows as the size of its input, usually called n, gets larger. It ignores machine speed and exact instruction counts, and instead focuses on the growth trend.

Why Big-O matters

Two programs can both work correctly, but one might slow down badly as the input grows while the other barely notices. Big-O gives you a common language to compare algorithms without running them on real hardware. When you choose between a data structure or a sorting method later in this course, Big-O is how you will justify the choice.

Reading Big-O

Big-O describes the worst-case growth rate of an algorithm as a function of n. It strips away constants and lower-order terms, because those matter less and less as n grows huge. For example, an algorithm that does 3n + 5 steps is still described as O(n), because the 3 and the 5 stop mattering once n is large.

Common complexities

Notation	Name	Example
O(1)	Constant	Accessing arr[0]
O(log n)	Logarithmic	Binary search
O(n)	Linear	Looping through an array once
O(n log n)	Linearithmic	Efficient sorting (merge sort)
O(n2)	Quadratic	Nested loops over the same array

As n grows, O(1) stays flat, O(n) grows in a straight line, and O(n2) grows much faster than either. An algorithm that is O(n2) on 10 items might feel instant, but on 1,000,000 items it can take far too long to finish.

Example: linear search

A linear search looks at each element one at a time until it finds a match, or reaches the end of the array. In the worst case it checks every element, so it is O(n). The example below counts how many steps the search actually takes so you can see the difference between the best case and the worst case.

#include <iostream>
using namespace std;

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

int main(void) {
    int arr[] = {4, 8, 15, 16, 23, 42};
    int n = 6;
    int steps;

    int index = linearSearch(arr, n, 42, steps);
    cout << "Found 42 at index " << index << " in " << steps << " steps" << endl;

    index = linearSearch(arr, n, 4, steps);
    cout << "Found 4 at index " << index << " in " << steps << " steps" << endl;

    return 0;
}

Output:

Found 42 at index 5 in 6 steps
Found 4 at index 0 in 1 steps

How it works

Searching for 42, which sits at the last index, forces the loop to check all 6 elements — the worst case, O(n). Searching for 4, which sits at index 0, finishes in a single step — the best case, O(1) for that particular run. Big-O notation always describes the worst case unless stated otherwise, so this whole function is classified as O(n): if the array had a million elements instead of 6, a search for a missing value would take roughly a million steps, growing directly in proportion to n.

Best, average, and worst case

You will sometimes see Big-O paired with words like “best case” or “average case”. Unless a lesson says otherwise, plain Big-O refers to the worst case, since that is the guarantee you can rely on when your program has to handle unpredictable input.

Big-O is the vocabulary you will use to compare data structures and algorithms for the rest of this section — the next lesson puts it to work by analyzing arrays and linked lists.