SFTPN: Big O Notation

Published on 13 May 2016 • Estimated reading time: 2 minutes

The series post, which contains more stuff formally trained programmers know, can be found here.

Big O Notation

This has always confused me and seemed out of my reach. It’s actually simple once I worked through it. Let’s start with the syntax:

O(n)

The "O" is just an indicator that we’re using Big O notation, and the n is the cost. Cost could mean various things—memory, CPU cycles—but most people think of it as the number of times the code will execute. The best cost is code that never runs (i.e., O(1)), though that likely has no practical value. To explain it, let’s look at a simple example:

Console.WriteLine("Hello 1");

The cost for that is 1, so we could write O(1). If we put that in a for loop like this:

for (var counter = 0; counter < 10; counter++)
{
    Console.WriteLine("Hello " + counter);
}

The cost would be 10, so we could write O(10).

n

Instead of being explicit with numbers (like 10 above), we can use shorthand notation. The common one is n, meaning it runs once per item. For our loop example, that means it could be written as O(n), so whether we loop 10 times or 100 times, the relative cost is the same and can be referenced the same way. From this point on, it’s just about adding math to it.

If we had a loop inside a loop—like this, running 100 times (10 × 10)—we could write it as O(n²).

var n = 10;
for (var outerCounter = 0; outerCounter < n; outerCounter++)
{
    for (var counter = 0; counter < n; counter++)
    {
        Console.WriteLine("Hello " + counter);
    }
}

Another common term used with Big O notation is log, i.e., logarithm, written like this: O(log n). Here, the cost per item decreases (relative to earlier items) as we add more.

[]

Further reading

The best guide I found was from Rob Bell.