Big O notation

Big O notation describes an asymptotic upper bound on how an algorithm’s resource usage grows with input size n. It’s a tool for reasoning about scalability, not a stopwatch.

CORE IDEAGrowth matters more than a single benchmark

An O(n) algorithm grows linearly with input size, while O(n²) grows quadratically. A slower-growing function often matters much more for sufficiently large inputs.

Explore the curves

INTERACTIVE / LIVE

Complexity explorer

Move the input-size slider and enable or disable growth curves.

Live demo

Input size n

20

Show complexity classes

O(1) O(log n) O(n) O(n²)

The lines show mathematical growth functions on a shared linear scale, not measured execution time.

Common complexity classes

The table is a quick reference. Each class describes how the work grows as the input gets bigger.

Class	Name	Example
O(1)	Constant	Array element access
O(log n)	Logarithmic	Binary search on sorted data
O(√n)	Square root	Simple trial division up to √n
O(n)	Linear	Scanning a list
O(n log n)	Linearithmic	Merge sort
O(n²)	Quadratic	Two nested loops over an input
O(2ⁿ)	Exponential	Naive enumeration of subsets
O(n!)	Factorial	Enumerating every permutation

IMPORTANTThe graph is not a benchmark

Constants, allocation overhead, cache behavior, and hardware can all change real runtime. The chart uses mathematical functions with a shared vertical scale.

Example: linear search

Here is a small C# method that checks each item until it finds the target.

C# | LinearSearch.cs

static int FindIndex(int[] values, int target)
{
    for (int i = 0; i < values.Length; i++)
    {
        if (values[i] == target)
            return i;
    }

    return -1;
}

The worst case examines all n items, so the time complexity is O(n). It uses O(1) additional space.

Continue learning

Try binary search to see how checking the middle of a sorted array reduces the remaining search range.