Monthly Archives: February 2016

Big O Notation Demystified

Our job as programmers is to solve real-world problems by writing algorithms. Often however there is more than one possible solution to a given problem.

For example, suppose you need to implement a Java interface defining a method to sort an array of integers:

public interface Sorter {
  public void sort(int array[]);
}

 
You could use any of the well-known sorting algorithms or even create a new one to solve the problem. But which implementation would you actually use in a production system? Provided there are no computer memory constraints you will want to use the most efficient solution i.e. the algorithm with the best average case performance in terms of running time.

If the size of the array is relatively small the difference in performance is probably negligible but it becomes more and more significant as the size of the array grows. The time taken by an algorithm to execute in relation to the size of the input is called time complexity of the algorithm and is commonly expressed using the big O notation. Evaluating algorithms in this way is called asymptotic analysis in computer science.

We can safely assume for the purposes of this discussion that an algorithm is equivalent to a method or function and that the input to an algorithm is the method or function argument. Measuring the size of the input of course will depend on the type of the argument. If the input is an array or higher-level collection its size is determined by the number of elements in the array or collection. If the input is a String object its size is determined by the number of characters in the string.

Now that we have defined the notion of time complexity let’s see how the big O notation is used to express some of the most common cases.

O(1) = Constant Time

As an illustration let’s consider the following Java method that returns the number of elements in an integer array:

public int elements (int[] array) {
  return array.length;
}

 
Whatever the size of the array passed as argument the time taken by this method to execute will be always the same as it performs only a single operation. The method is said to run in constant-time and its time complexity is expressed as O(1).

O(n) = Linear Time

If the running time of a method increases in line with the input size the method is said to run in linear time and its time complexity is expressed as O(n).

An example of linear time complexity is the following Java method that calculates the sum of all the elements in an integer array:

public int total (int[] array) {
  int total = 0;
  for (int index = 0; index < array.length; index++) {
    total += array[index];
  }
  return total;
}

 
For instance given an input size of 256 this method will perform 256 x operations.

O(log n) = Logarithmic Time

Computers use a binary numeral system in which numbers are represented by sequences of 0 (zero) and 1 (one) also known as the base-2 numeral system.

The base 2 is used everywhere in computer science. For instance to work out how many positive integer numbers you can represent with an 8-bit word you raise the base 2 to the power of 8 to obtain 256 i.e. 2^8 = 256.

The logarithm operation does the inverse of exponentiation. It returns the exponent to which the base 2 must be raised to produce a number. For instance log(256) = 8.

Methods that run in logarithmic time are much more efficient than linear ones. Whereas a linear time method with an input size of 256 will perform 256 x operations, a logarithmic time method will only need to perform 8 x operations with the same input size.

Searching a binary tree is an example of time complexity of O(log n).

O(n log n) = Linearithmic Time

Given an input size of 256 a method that runs in linearithmic time will perform 2,048 x operations:

n * log(n) = 256 * log(256) = 256 * 8 = 2,048

The merge sort algorithm is an example of time complexity of O(n log n).

O(n^2) = Quadratic Time

Given an input size of 256 a method that runs in quadratic time will perform 65,536 x operations:

n ^ 2 = 256 ^ 2 = 65,536

The bubble sort algorithm is an example of time complexity of O(n^2).

The above are some of the most common time complexity measures. You can see more examples on the Big O Cheat Sheet website.

We have been assuming so far that the choice of algorithm is based solely on its time complexity without taking into account any other resource constraints.

However the amount of memory required by an algorithm is also an important decisional factor. The amount of working storage an algorithm needs in relation to the size of the input is defined as the algorithm’s space complexity and it is also commonly expressed using the Big O notation.

There is often a trade-off between time and space requirements, and in practice both need to be taken into account when selecting an algorithm.