Update 2024-09-05: I have updated this post to contain some coding examples as a way to better describe differing complexities.

What is Big O Notation?

A mathematical notation we use to describe the time complexity or space complexity of an algorithm. It provides a way to analyse and compare the efficiency of different algorithms by looking at how their performance scales with the input size.

In short, it’s a reasonably straightforward way to analyse the efficiencies of algorithms, based purely on instruction sets.

The most general expression would be expressed as a function O(n) but let’s look at more common expressions.

O(1) - Constant time

The algorithm’s performance does not depend on the input size. It executes in a constant amount of time, regardless.

A simple example of this would be accessing an element in an array by index.

public class Example
{
    public int GetElementAtIndex(int[] array, int index)
    {
        // Accessing an element by index in an array is O(1)
        return array[index];
    }
}

O(n) - Linear time

The algorithm’s performance scales linearly with the input size.

As an example, iterating through the abovementioned array and performing a constant-time operation on each element.

public class Example
{
    public int FindMax(int[] array)
    {
        var max = 0;

        // Iterating over each element in the array is O(n)
        for (int i = 0; i < array.Length; i++)
        {
            var value = GetElementAtIndex(array, i);
            if (value > max)
                max = value;
        }

        return max;
    }
}

O(n^2) - Quadratic time

Now the algorithm’s performance is scaled directly proportional to the square root of the input size.

This often occurs in nested loops. Where each iteration contributes to the overall complexity of the algorithm.

public class Example
{
    public int FindMax(int[][] array)
    {
        var max = 0;

        for (int i = 0; i < array.Length; i++)
        {
            // Iterating through each array in the 2-dimensional array gives us O(n^2)
            for (int j = 0; i < array[i].Length; i++)
            {
                var value = GetElementAtIndex(array[i], j);
                if (value > max)
                    max = value;
            }
        }

        return max;
    }
}

O(log n) - Logarithmic time

With logarithmic time, the algorithm’s time increases, but at a slower rate.

This graph uses considerably larger input sizes to better demonstrate the effect.

Now we’re talking about algorithms that divide the problem space in half at each step. Think of something like a binary search.

public class Example
{
    public int BinarySearch(int[] array, int target)
    {
        int left = 0;
        int right = array.Length - 1;

        while (left <= right)
        {
            int mid = left + (right - left) / 2;

            if (array[mid] == target)
            {
                return mid; // Target found
            }

            if (array[mid] < target)
            {
                left = mid + 1; // Search the right half
            }
            else
            {
                right = mid - 1; // Search the left half
            }
        }

        return -1; // Target not found
    }
}

O(n!) - Factorial time

We’ve hit the worst-case scenario where performance grows factorially with the input size.

The only example I can think of is iterating through an array and running a quadratic time algorithm on each element as well as all previous elements in the array (on every iteration), or generating all permutations of a set:

public class Example
{
    public void GeneratePermutations(int[] array)
    {
        Permute(array, 0, array.Length - 1);
    }

    private void Permute(int[] array, int start, int end)
    {
        if (start == end)
        {
            Console.WriteLine(string.Join(", ", array));
        }
        else
        {
            for (int i = start; i <= end; i++)
            {
                Swap(ref array[start], ref array[i]);
                Permute(array, start + 1, end);
                Swap(ref array[start], ref array[i]); // Backtrack
            }
        }
    }

    private void Swap(ref int a, ref int b)
    {
        int temp = a;
        a = b;
        b = temp;
    }
}

Bear in mind, just because it’s worst-case scenario doesn’t mean that it’s always avoidable. Think of brute-forcing a password, the reason it can take so long is because it’s likely running on factorial time.

How does Big O help us?

It’s important to keep in mind that Big O described the upper bound (or worst-case scenario) of an algorithm’s complexity. It’s not designed to be a benchmarking tool, it wouldn’t be effective at all, instead, it’s a useful tool for comparing algorithms and making informed decisions about which one to use. A high complexity doesn’t always indicate that there has to be a better way (though there could be).

If you’ve never found yourself with multiple correct answers to a problem, not knowing which one would be better to implement, I envy you.