Big O notation overview by example

This is great article of basic things about big O notation. Big O notation is used for describing the complexity of algorithm, or the cost of doing something in worst case. Just want to sum up here.

O(1) - constant cost

Doing something always costs the same constant amount of effort, no matter how difference input is.

bool IsFirstElementNull(IList<string> elements)
{
    return elements[0] == null;
}

O(N) - linear cost

Cost of algorithm linearly depends on size of input.

bool ContainsValue(IList<string> elements, string value)
{
    foreach (var element in elements)
    {
        if (element == value) return true;
    }

    return false;
}

In the best case, this algorithm takes 1 effort (comparison) to return result.
In the worst case, this algorithm takes n effort (length of array) to return result.
So it is O(N).

O(N²)

bool ContainsDuplicates(IList<string> elements)
{
    for (var outer = 0; outer < elements.Count; outer++)
    {
        for (var inner = 0; inner < elements.Count; inner++)
        {
            // Don't compare with self
            if (outer == inner) continue;

            if (elements[outer] == elements[inner]) return true;
        }
    }

    return false;
}

In the worst case, this algorithm takes n * n effort to return result.
It takes n iterations to go through all items in outer loop. For each iteration, need again go through all items in inner loop. It take n * n steps. So it is O(N²).
Simple words:

• 2 layers of loop: O(N²)
• 3 layers of loop: O(N³)
• 4 layers of loop: O(N⁴)
• and so on

O(2ⁿ)

int test(int number)
{
    if (number == 0) return number;

    return test(number - 1) + test(number - 1);
}

Cost will doubles each time we increase size of data by 1. Because each step will call 2 function recursively:

• number = 0: 1 step (return expression)
• number = 1: 2 steps i.e. 2 function calls test(0)
• number = 2: 4 steps i.e. 2 function calls test(1), each has 2 function calls test(0)
• number = 3: 8 steps i.e. 2 function calls test (2), each has 2 test(1) and each has 2 test(0)

O(log(n))

Quite hard to explain by word. Let’s see this example from SOF:

while (n > 0) {
   n/=2; 
}

Demonstration

2^k = n -> k = log(n)
So we have O(log(n))