Big O Notation

This is another entry in my series covering all things data structures and algorithms. While my first couple articles were around data structures, my upcoming posts will focus more on algorithms. Before you can start analyzing algorithms, first its important to cover Big O notation.

I am going to write this post with my coworker in mind. He mentioned an interest in learning about Big O notation. However, anything that starts to make its way into the realm of math turns him off of the subject. While you can't cover Big O without touching some math, I am going to try to keep it at a min and hit only the basics.

What is Big O Notation?

Big O notation is a way of measuring the efficiency of an algorithm as it's input size approaches infinity. In terms of what we are measuring, it can be either the time or space complexity of an algorithm. Time being the runtime of an algorithm, and space being the memory. In this post we will be focusing on measuring runtime.

Big O is often referred to as measuring the "worst case" scenario. There are other types of notation that denote other measures like the "best case" or "average case". But in terms of measuring efficiency its usually more helpful to think in terms of worst case scenarios.

Big O Basic Example

Lets look at the basic code snippet.

public void PrintList(List<int> list)
{
    foreach(var entry in list)
    {
        Console.WriteLine(entry);
    }
}

This function takes an list, and prints every element to the console. The first thing you need to do is break the function into parts.

1. This function has a for loop, that loops through ever element in the array passed in. If we denote the size of the array as n, then we can say that the for loop runs n times.
2. We can therefore say that every line inside the for loop runs n times. Since the only line inside the loop is a print statement, we can say the print statement runs n times.

You can see this more clearly with the function rewritten below with some notes:

public void PrintList(List<int> list) //Pass in a list of length n
{
    foreach(var entry in list) //Loop through n times
    {
        Console.WriteLine(entry); //Meaning we print n times
    }
    //n operations total
}

Because this function does nothing else other than print to the screen n times, we can say that this function runs in O(n) time.

Lets look at another example that's has a bit more complexity.

public void PrintList(List<int> list)
{
    foreach(var entry in list) //Loop through n times
    {
        Console.WriteLine(entry); //We print to the screen n times
        int square = entry * entry; //we perform a math function n times
        Console.WriteLine("The Square is {0}", square); //We print to the screen n times
    }
    Console.WriteLine("Goodbye!"); //We print to the screen once.
}

Here you can see with print to the screen n times just like our last example. We also print to the screen a second time in the same loop, as well as perform a mathematic operation. Thats 3 operations total, all in the loop that runs n times. You can think of this as n + n + n = 3n.

The final line of the function prints to the screen only once. Because this only happens once no matter the input size, we can simply denote that as 1. This is also referred to as Constant time, but we will get to that later.

So adding these together, this function runs 3n + 1.

Now when you look at this, you might be thinking we are getting dangerously close to math. Luckily this can be simplified. Remember before when we mentioned that Big O tracks worst case? It's a measurement of how the input size grows and approaches infinity.

So imagine n grows to infinity. The nice thing about infinity is its, well, infinite. Doing things like multiplying it by 3 or adding 1 to it makes no difference. So for Big O, we can drop all coefficients and constants when analyzing our function. The end result is n, or more formally, O(n).

Big O Notation Runtimes

When we see a function that runs in O(n) time, we say it runs in linear time. This is because as the input size grows, the time grows linearly. We can see this in a graph that charts time over input. While linear time is a basic example, but there are multiple runtime results.

Constant

Constant time, O(1), runs the same regardless of the input size. Take the function below as an example.

There are 5 steps in this function. They don't vary based on the input size. And while it might seem like you should call this O(5), in our effort to simplify, we call it O(1).

Logarithmic

Logarithmic time, O(logn), is usually characterized by iterating through a subset of the elements. Binary search is a good example, or recursively calling a function where each time you pass in a subset of a list.

Linear

Linear time, O(n), is characterized by linear growth as the input grows. If our function loops through a list, and performs 10 operations in that loop, then with a list of length 5, then it performs the operations 50 times in total. If we scale up the input size to 50, then the number of operations grows linearly at the same rate, to 500.

Linearithmic

Linearithmic time, O(nlogn), usually consists of running some operation or function that runs in logarthmic time, n times. One of the most common examples of this is Merge Sort.

Quadratic

Quadradic time, O(n2), is characterized by running n operations n times. This can most easily be visualized as a nested for loop, where each loop runs n times. Insertion sort and Bubble sort both run in quadratic time.

Cubic

Exponential

Factorial

Considerations When Analyzing Your Code

While the examples we looked at are actual code, they are rarely functions you would run into in your day to day. It's easy to look at examples like these online and try to apply them directly to your solution. But there are some things you need to keep in mind.

First is to keep in mind functions built into your language or framework. For example, if you have a list or an array, and you use a function such as where, select, or contains, remember that it also abides by the rules of Big O notation. If you want to see if a list contains an element, you start going through each element of the list, and stop when you find the element you want. In the worst case scenario, the item you are looking for is the very last element. Meaning you need to go through ever element. That means you are running in O(n) time. Now imagine you are doing that contains in a separate for loop. You need to take into consideration how this will effect the calculation of the Big O notation.

Another thing to remember is that you rarely have an instance where you have a single function running in isolation. Sure if you want to just look at the efficiency of a single algorithm, you can focus on it only. But what if you are trying to analyze an entire application? What if your function is being called from inside a for loop in another function? Its helpful to look at your application as a whole to get an accurate understanding of its runtime.

Another mistake people make is making things inefficient when trying to make them efficient. For example, we walked through the example of how a function like contains on a list runs in O(n) time. Well instead of a list, you could use something like a set or dictionary. Lookups in a dictionary or set run in constant time (O(1)). This is because they use a key or hash to find the value in the collection. Knowing that, you may be incline to convert all the lists you can to sets. This isn't a bad idea if you can switch the type of the list. But switching the type is different than converting it. If you already have a list, then convert it to a set right before you do your lookup, you wasted time in during the conversion itself. Probably enough time to make it so you won't see any improvements in efficiency at all. So make sure you are smart about how you try to improve your algorithms.

Finally, you need to remember that Big O is a measurement of efficiency at the extreme. If you look at the graph of the different runtimes, you will notice its not so clear as the input size is smaller. This is because at smaller input sizes, coefficients and constants that we removed will actually have an effect. The differences might not become apparent till you reach the thousands or even millions. So don't only rely on Big O evaluation on smaller inputs.

Thanks to #WOCinTech for the teaser photo used in this post!