“green plant beside white desk” by Johnson Wang on Unsplash

WTF is Big O notation?

BigO is an equation that describes how the run-time scales with respect to input variables. Big O is about the way to determine the efficiency of an algorithm over time.

Pigeon transfer speed is O(1), is constant time with respect to the size of the input. Simply, a pigeon flying data from A to B takes the same time regardless of the size of input/data.

Using the same example, Internet time is O(n). (Linear) This means it scales linearly with respect to the amount of input. Twice the amount of data inputted will take twice the amount of time.

An algorithm’s efficiency can be defined in terms of the problem’s size and processing step. A growth function shows the relationship between two. An example of a growth function:

f(n) = 2n² + 4n + 6

For example, the function below prints all pairs of values in the array.

function printPairs(array) {
forEach x in array {
 forEach y in array {
  print x, y
  }
 }
}

This will take O(n²), where n is the size of the array. Therefore, the amount of time to run that function will increase in respect to n².

Run-time to mow a square plot of grass would be:

O(a) and O(s²).

O(a) where a = area of grass

O(s²) where s = length of one side

O(a) and O(s²) are equivalent since a = s².

Big O rules:

1. Different steps get added

eg. a function with two steps: O(a) and O(b) is equal to O(a+b)

function something() {
 doStep1();
 doStep2();
}

2. Drop constants

Both of these are O(n). Drop constants (eg. O(2n)), because you are looking at how the algorithms scale roughly.

function minMax1(array) {
 min, max <= null
 forEach element in array
 min = Min(element, min)
 forEach element in array
 max = Max(element, max)
}
function minMax2(array) {
 min, max <= null
 forEach element in array 
 min = Min(element, min)
 max = Max(element, max)
}

One finds min and max simultaneously while the other finds Min and Max one after the other.

3. If you have different inputs, use different variables

function intersectionSize(arrayA, arrayB) {
  let count = 0;
  for element in arrayA {
    for element in arrayB {
      for a == b {
        count = count + 1
      }
     }
    }
  return count
}

Big O is an equation that expresses how runtime changes and how it scales. n here is not the length of the array IF there are two arrays.

This algorithm is O(a * b) where a is the length of arrayA and b is the length of arrayB

4. Drop non-dominant terms

What is a dominant term? It is a term which increases most quickly as the problem increases. We use the dominant term to determine ‘asymptotic complexity’.

Growth function:

f(n) = 2n² + 4n + 6

As the table above shows, as n increases, the term 2n² dominates the result of the function, f(n). 2n² is our dominant term here, because it is the one that increases in value the quickest.

Logically, this also roughly means:

Big O = Asymptotic Complexity = Dominant Term

Asymptotic complexity is also known as the ‘order of the algorithm’, where ‘order’ here means ‘approximately’. We are only interested in the dominant term, and that is why we can safely ignore other terms (n) and constants (ie. 2, 6). Therefore, this growth function’s Big O is O(n²).

function (array) {
let max = null
// this takes O(n) time
  forEach element in array {
   max = Max(element, max)
  }
print max
// this takes O(n²) time
  forEach elementA in array {
    forEach elementB in array {
      print elementA, elementB
       }
     }
   }

The first step takes O(n) time and the second step takes O(n²). This algorithm can be described as O(n + n²).

Logically, O(n²) < O(n + n²) < O(n² + n²).

See graph below, which illustrates number of operations N versus input size n for each function:

What are the implications of Big O?

In summary, Big O is used to analyse algorithms and determine which ones are faster or slower in comparison ie. run-time vs input size.