An Intuitive Explanation of Big-O

In what follows is an intuitive (hopefully!) and concise discussion of big-O. I try to first explain what big-O is: a way of estimating how long an algorithm will take to run to completion given the "worst" possible input. I then give a few examples of how to compute the big-O of an algorithm. All code samples are in JavaScript.

Introduction

An algorithm is a list of instructions to complete some task. An example of an algorithm is a recipe. A data structure is a way of organizing data. A family tree is a type of data structure. It organizes the relationships amongst familial relatives in an intuitive and hierarchical way.

Big-O

Big-O is a measure of how long an algorithm takes to run to completion. Let's consider an example.

The following algorithm, isOneInArray takes an array of integers as input. It returns true if a 1 IS in the array and returns false if the number 1 IS NOT in the array. Remember that an integer is a number that can be written without a fractional component, like 4 or 1000.

function isOneInArray(array) {
  for (let index=0; index<array.length; index++) {
    let currentItem = array[index];
    if (currentItem === 1) {
      return true;
    }
  }
  return false;
}

Before we proceed any further let's construct a simple mental model of a CPU or Central Processing Unit. The CPU is what does "logical" computations on our computers. Our model of a CPU will ascribe the following properties to a CPU:

1. A CPU only does comparisons that result in a Boolean (e.g., 1 !== 2 results in true); comparisons include !==, ===, >, <, etc. Our CPU compares at most two values.
2. A CPU can only do ONE of these comparisons at a time.

Note: This is a gross oversimplification of how a CPU actually works, but is close enough for the purposes of this discussion.

Let's consider a sample input for the isOneInArray function:

isOneInArray([5,4,3,2,1])

What is our CPU doing here?

If we take a look at our implementation of the isOneInArray function we can see that the CPU is being "asked" to compare each member in the array above. This is a total of 5 comparisons because there are 5 integers in the array. What the CPU is doing during the execution of the isOneInArray function can be written as follows:

Is 5 equal to 1? No. Next item in array.
Is 4 equal to 1? No. Next item in array.
Is 3 equal to 1? No. Next item in array.
Is 2 equal to 1? No. Next item in array.
Is 1 equal to 1? Yes. Return true!

This was 5 comparisons.

It is important to note that the number of comparisons equals the number of elements in the array. If we wanted to generalize we could say that the number of comparisons that our isOneInArray function does is equal to N, where N is some positive integer that is equal to the length of the input array.

Therefore we say isOneInArray is O(n).

If we were to graph the number of comparisons done by our CPU against the length of an input array it would look like this:

This is a linear line with a slope of 1. For this reason we say that our isOneInArray algorithm is O(n) where n is the length of the input array. The only thing affects the number of comparisons our CPU does is the length of the input array.

One important thing to note is that whenever we are considering big-O we consider the worst possible input on an algorithm. We can pretend that we have some evil genius adversary that is providing us with the input that would require us the most possible comparisons in our algorithm. A worst-case input for isOneInArray would have the 1 at the very end of the array.

We can also write functions that are O(n²), O(nlogn) and O(constant). Remember the n², nlogn and constant are all just factors that we can multiply by an input array's length to get the number of comparisons an algorithm has to do.

Let's consider an algorithm with a nested for-loop like this:

function isTwoInArray(nestedArray) {
  for (let index=0; index<nestedArray; index++) {
    for (let k=0; index<nestedArray[index]; k++) {
      if (nestedArray[index][k] === 2) {
        return true;
      }
    }
  }
  return false;
}

How many comparisons will the above function make when given the following input:

isTwoInArray([[6,5,4], [3,1,2]])

Generally speaking when determining big-O we can use the following expressions:

O(n^{# of nest for-loops})

Conclusion

This was an informal and not mathematically rigorous introduction to big-O. There are many more mathematically rigorous and in-depth resources on algorithms and asymptotic complexity. One of my favorites in Introduction to Algorithms by C.L.R.S.

Thanks for reading!