Beiginner's guide for Big O notation


Big O notation describes the performance or complexity of an algorithm. It shows the worst-case scenario and the execution time required or the storage space used by an algorithm too.

Hopefully, this article will help you understand the basic of Big O notation with JavaScript sample code.

😼 O(1)

O(1) shows the execution time(or space) of an algorithm is always same regardless of the size of the input data set.

function isFirstElementNull(elements) {
  return elements[0] === null;
}

🐞 O(N)

O(N) illustrates an algorithm’s performance will grow linearly and in direct proportion to the size of the input data set. The example is as follows:

function findValue(elements, expect) {
  for (let e of elements) {
    if (e === expect) { return true; }
  }
  return false;
}

In Big O notation, we should always assume the upper limit where the algorithm will perform the maximum number of iterations. So, in that case, the worst case is return false after finishing the loop.

🚜 O(N**2)

O(N**2)(N squared) describes an algorithm whose performance is directly proportional to the square of the size of the input data set. This is common with algorithms that involve nested iterations. O Notation of deeper nested iteration will be O(N**3), O(N**4) or etc.

function hasDuplicatedValue(elements) {
  for (let outerIndex = 0; outerIndex < elements.length; outerIndex++) {
    for (let innerIndex = 0; innerIndex < elements.length; innerIndex++) {
      if (outerIndex !== innerIndex && elements[outerIndex] === elements[innerIndex]) {
        return true;
      }
    }
  }
  return false;
}

🐮 O(2**N)

O(2**N) represents an algorithm whose growth doubles with each addition to the input data set and it’s exponential.

function fibonacci(number) {
  if (number <= 1) return number;
  return fibonacci(number - 2) + fibonacci(number - 1);
}

🎉 O(log N)

Big O notation of Binary search like following example is O(log N).

function binarySearch(elements, expect) {
  let firstIndex = 0;
  let lastIndex = elements.length - 1;
  let middleIndex = Math.floor((lastIndex + firstIndex)/2);

  while(elements[middleIndex] !== expect && firstIndex < lastIndex) {
    if (expect < elements[middleIndex]) {
      lastIndex = middleIndex - 1;
    } else if (expect > elements[middleIndex]) {
      firstIndex = middleIndex + 1;
    }
    middleIndex = Math.floor((lastIndex + firstIndex)/2);
  }

  return (elements[middleIndex] === expect) ? middleIndex : -1 ;
}

const elements = [1, 2, 3, 4, 5, 7, 8, 9];
console.log(binarySearch(elements, 5)); // => 4
console.log(binarySearch(elements, 10)); // => -1

O(log N) algorithm like the binary search denotes produces a growth curve that peaks at the beginning and slowly flattens out as the size of the data sets increase. This makes algorithms extremely efficient when processing with large data sets.

🏈 Special Thanks

I wrote this article referencing A beginner’s guide to Big O notation - Rob Bell.

In addition, I could understand it with the following articles:

🖥 Recommended VPS Service

VULTR provides high performance cloud compute environment for you. Vultr has 15 data-centers strategically placed around the globe, you can use a VPS with 512 MB memory for just $ 2.5 / month ($ 0.004 / hour). In addition, Vultr is up to 4 times faster than the competition, so please check it => Check Benchmark Results!!

Next