Understanding Big O notation

An algorithm refers to a process for going about a particular operation. Often, there is more than one way to achieve a particular computing goal. The selection of a particular algorithm can make our code either fast or slow – even to the point where it stops working under a lot of pressure.

One way to analyze competing algorithms is to count the number of steps each one takes. The number of steps that an algorithm takes is the primary factor in determining its efficiency.

In order to ease communication regarding time complexity, computer scientists have borrowed a concept from the world of mathematics to describe a concise and consistent language around the efficiency of data structures and algorithms. Known as Big O Notation, this formalized expression around these concepts allows us to easily categorize the efficiency of a given algorithm and convey it to others.

Big O achieves consistency by focusing on the number of steps that an algorithm takes.

O(1)

Many pronounce this verbally as “Big Oh of 1”, others call it “Order of 1”. While there is no standardized way to pronounce Big O Notation, there is only one way to write it.

O(1) simply means that the algorithm takes the same number of steps no matter how much data there is. For example, reading from an array takes just one step no matter how much data the array contains. On an old computer, that step may have taken twenty minutes, and on modern hardware, it may take just a nanosecond. But in both cases, the algorithm takes just one single step.

O(N)

This is a way of saying that for N elements inside an array, the algorithm would take N steps to complete.

Big O Notation does more than simply describe the number of steps that an algorithm takes, rather, it describes how many steps an algorithm takes based on the number of data elements that the algorithm is acting upon. Another way of saying this is that Big O answers the following question: how does the number of steps change as the data increases?

An algorithm that is O(N) will take as many steps as there are elements of data. So when an array increases in size by one element, an O(N) algorithm will increase by one step. An algorithm that is O(1) will take the same number of steps no matter how large the array gets. Because the number of steps remains constant at O(1) no matter how much data there is, this would be considered constant time. Even if an algorithm technically takes 3 or 5 steps rather than just 1 step, Big O Notation considers this algorithm as O(1) as long as the number of steps remains constant. It follows that even a 100 step algorithm would be expressed as O(1).

The best-case scenario of an algorithm refers to the time an algorithm performs at its best and takes as fewer steps as possible to perform an operation. Like inserting an element at the end of an array. In contrast, the worst-case scenario refers to the worst performing time.

While Big O effectively describes both the best- and worst-case scenarios of a given algorithm, Big O Notation generally refers to worst-case scenario unless specified otherwise. The reason for this would be that knowing exactly how inefficient an algorithm can get in a worst-case scenario prepares us for the worst and may have a strong impact on our choices.

There are also algorithms that fall somewhere in between O(1) and O(N). In Big O, these algorithms are described as having a time complexity of O(log N). These type of algorithms are known as having a time complexity of log time.

Simply put, O(log N) is the Big O way of describing an algorithm that increases one step each time the data is doubled.

To understand why a given algorithm is called “O(log N)”, we need to first understand what logarithms are. Log is shorthand for logarithm. The first thing to note is that logarithm has nothing to do with algorithms, even though the two words look and sound similar. Logarithms are the inverse of exponents. Here’s a quick refresher on what exponents are:

23 is equivalent to, 2 * 2 * 2, which just happens to be 8.

Now, log2 8 is the converse of the above. It means, how many times do you have to multiply 2 by itself to get a result of 8?

Since you have to multiply 2 by itself 3 times to get 8, log2 8 = 3.

Here’s another example:

26 translates to: 2 * 2 * 2 * 2 * 2 * 2 = 64

Since, we had to multiply 2 by itself 6 times to get 64, log2 64 = 6.

There is an alternative way of describing the same concept to wrap our heads around this more easily.

Another way of explaining log2 8 is: if we kept dividing 8 by 2 until we ended up with 1, how many 2s would we have in our equation?

8 / 2 / 2 / 2 = 1

In other words, how many times do we need to divide 8 by 2 until we end up with 1?

In this example, it takes us 3 times. Therefore, log2 8 = 3.

Similarly, we could explain log2 64 as: how many times do we need to halve 64 until we end up with 1?

64 / 2 / 2 / 2 / 2 / 2 / 2 = 1

Since there are 6 2s, log2 64 = 6.

Here’s a simple JavaScript function to determine the logarithm of a given number:

function log2(num) {
  var count = 0
  while (num > 1) {
    num = num / 2
    count++
  }

  return count
}

Now that we understand what logarithms are, the meaning behind O(log N) will become clear.

Whenever we say O(log N), it’s actually shorthand for saying O(log₂ N). We’re just omitting that small 2 for convenience.

Recall that O(N) means that for N data elements, the algorithm would take N steps. If there are eight elements, the algorithm would take eight steps.

O(log N) means that for N data elements, the algorithm would take log₂ N steps. So, if there eight elements, the algorithm would take three steps, since log₂ 8 = 3.

Said another way, if we keep dividing the eight elements in half, it would take us three steps until we end up with one element.

While the O(N) algorithm takes as many steps as there are data elements, the O(log N) algorithm takes just one additional step every time the data elements are doubled.

This was an easy-to-understand approach to the topic of Big O. Big O is originally a concept of mathematics, and therefore it is often described in mathematical terms. For example,

The big-Oh notation allows us to say that a function f(n) is less than or equal to another function g(n) up to a constant factor and in the asymptotic sense as n grows towards infinity. If f(n) is of the form of An + B, where A and B are constants. It’s called a linear function, and it is O(n).

The big-Oh notation gives an upper bound on the growth rate of a function. The statement “f(n) is O(g(n))” means that the growth rate of f(n) is no more than the growth rate of g(n).

For further reading and to dig further into the math behind Big O, check out:

• this article provides a pretty good definition of big-Oh.
• Wikipedia article on Big O, taking a fairly heavy mathematical approach.