Big-O Notation. Beginner guide.

Big O is a measure of the computational efficiency of an algorithm. It is measured in 2 ways:

Time Complexity — How many operations are performed?

Space Complexity — How much space is used?

Programmers aren’t usually concerned with how well an algorithm can perform as much as they are concerned with how badly it can perform, i.e. the worst-case scenario.

Consider the find method. If the target is at the beginning, great! It runs once. However, if the target is at the end, it runs n number of times, n being the length of the array. We would consider the time complexity of this algorithm to be O(n) (O of n).

Note: When people talk about Big O, they can really mean one of 2 things: worst-case scenario or average-case scenario. For the most part, most people are talking about the worst-case scenario when they talk about Big O, so we will stick with that.

Measuring Big O.

Big O notation looks like the following:

O(x) — in which x is the value denoting the efficiency.

Here are some typical values:

1. Constant Complexity O(1) — The best complexity. The operation time/space is constant and does not increase or decrease based on input (e.g. most basic operations, accessing a value in a hash):

function printFirstItem(items) {
  console.log(items[0]);
}

2. Linear Complexity O(n) — Operation time/space increases at a 1:1 rate as the input gets larger. (e.g. mapping/filtering over an array):

function printAllItems(items) {
items.forEach(item => {
    console.log(item);
  });
}

Another example of linear complexity:

function sayHiNTimes(n) {
  for (let i = 0; i < n; i++) {
    console.log('hi');
  }
}

function printAllItems(items) {
  items.forEach(item => {
    console.log(item);
  });
}

Both of these functions have O(n) runtime, even though one takes an integer as its input and the other takes an array.

3. Exponential Complexity O(n^x) — Operation time/space increases exponentially with input size (e.g. nested iterations / loops):

function printAllPossibleOrderedPairs(items) {
items.forEach(firstItem => {
    items.forEach(secondItem => {
      console.log(firstItem, secondItem);
    });
  });
}

4. Logarithmic Complexity O(log(n)) — Operation time/space increases logarithmically (more efficient than linear). (e.g. traversing a binary tree)

We don’t care about multipliers/divisors. An algorithm that performs at O(n/2) or O(3n) is still considered to be O(n).

function log(n) {
    for (let i = 1; i < n; i*=2) {
        const result = i;
        console.log(result);  
    }
}

In conclusion, with Big-O notation, we express the runtime in terms of— how quickly it grows relative to the input, as the input gets arbitrarily large.