Understanding Big O Notation Using JavaScript.

• What is Big O Notation?
• Time Complexity
• Simplifying Big O Expressions
  • Rules of thumb
• Space Complexity
  • Rules of thumb
• Summary
• Resources

In this article, We will understand the Big O Notation using Javascript.

What is Big O Notation?

Every problem has many different solutions.

Example

Write a function that takes a string as an input and returns a reversed copy.

If I asked 100 people to solve this problem I may get more than 10 solutions with very different approaches.

Click here to see the solutions on Stack Overflow.

So, how do we know what is the best one?

Here comes the rule of Big O Notation.

So, Big O Notation — or Big O for short is about comparing code to know which one is the best.

But the question you may ask right now, what does The Best mean?

Is the fastest code the best? Or maybe the code which less memory-intensive is the best? Or maybe the more readable code is the best?

Actually, there is no “The Best” answer for the “The Best” code, but in general, we all want our code to be as fast as possible, readable, and takes less space in memory right?

So, here comes these two expressions:

• Time Complexity.
• Space Complexity.

Time Complexity

Write a function that calculates the sum of all numbers up to and including some number n.

Solution 1

function getSum1(n) {
  let sum = 0;

  for (let i = 1; i <= n; i++) {
    sum += i;
  }

  return sum;
}

Solution 2

function getSum2(n) {
  return (n * (n + 1)) / 2;
}

As you can see the two solutions are absolutely different. The first one includes a loop and the second one doesn’t. The second one is much shorter which does not necessarily make it better. And with both solutions, we will get the same results.

getSum1(3); // 6
getSum2(3); // 6

So, which one of them is better in Time Complexity? in the other words which one is faster?

We can use performance.now() method to calculate the times each function takes to execute.

let t0 = performance.now();
getSum1(10000);
let t1 = performance.now();

console.log("getSum1 took " + (t1 - t0) + " ms.");

// Output:
// getSum1 took 4.944999993313104 ms.

let t0 = performance.now();
getSum2(10000);
let t1 = performance.now();

console.log("getSum1 took " + (t1 - t0) + " ms.");

// Output:
// getSum2 took 0.050000002374872565 ms.

As you can see, in my machine getSum2 took way less time than getSum1.

This way of comparing the time between these two codes is not consistent simply because different machines will record different times.

Also, the same machine will record different times.

And in another scenario, a piece of code might take a long time to execute

So, it’s not the best solution to run and calculate the time of each code to know which one is faster.

It must be another way to calculate the time, and that is where Big O Notation comes in.

So, rather than counting seconds which are variable,

Let’s count the number of Operations that the computer has to perform.

If we take a look at the second solution:

function getSum2(n) {
  return (n * (n + 1)) / 2;
}

We have 3 operations

• 1 Multiplication (*)

• 1 Addition (+)

• 1 Division (/)

The number of operations will be O = 1 + 1 + 1.

And there will always be these 3 operations regardless of the size of n is.

Compering to the first solution:

function getSum1(n) {
  let sum = 0;

  for (let i = 1; i <= n; i++) {
    sum += i;
  }

  return sum;
}

We will have:

• 1 assignment => sum = 0.

• 1 assignment => let i = 1.

• n addition and n assignment => sum += i.

• n addition and assignment => i++.

• n comparison => n<=n.

The number of operations will be O = 5n + 2.

Yes, it’s hard to count the number of operations, but regardless of the exact number, in Big O we focus on the big picture.

We don't really have to know the exact number of operations, it’s enough for us to know that the number of operations increases proportionally with the number of n.

Big O allows us to talk formally about how the runtime of an algorithm grows as the inputs of a function grow.

So, we can formulate the previous equation O = 5n + 2
to be O(n).

by removing all the constants (the number 5 and the number 2 ).

And O(n) represents Linear Time Complexity.

And the graph for this will be:

Compering of the first equation of the getSum2 function O = 3

We can formulate it to be O(1)
Since the number 1 represents a constant
and O(1) represents Constant Time Complexity.

And the graph for this will be:

Another Example

function nestedLoop(n) {
  for (let i = 0; i <= n; i++) {
    for (let j = 0; j <= n; j++) {
      console.log(i, j);
    }
  }
}

This example has a Nested Loop, in other words, it’s O(n) inside O(n)

So, it will be O(n²).

And O(n²) Represents Quadric Time Complexity.

And the graph for this will be:

Simplifying Big O Expressions

1. Constants don’t matter

O(2n) => O(n)

O(900) => O(1)

O(19n²) => O(n²)

1. Smaller Terms Don’t Matter

O(5 + n) => O(n)

O(2n +7) => O(n)

O(2n + n² + 74) => O(n²)

Rules of thumb

Constant Time Complexity O(1)

// 1. Mathematical Operations
let i += 5;

// 2. Variable Assignments
let i = 7;

// 3. Accessing elements in an array by index
let ar = [1, 2, 3];
let x = ar[3]; // <==

// 4. Accessing element in an object by key
let obj = { firstName: "Youssef" };
let fName = obj.firstName // <==

Linear Time Complexity O(n)

All kind of loops

• for loop
• Array.map
• Array.forEach
• Array.indexOf
• ...etc

Quadric Time Complexity O(n²)

• nested loops

And there are more types of Time Complexity but these three are the most common ones.

Space Complexity

We can also use Big O to calculate Space Complexity (The amount of memory taken).

I’m not talking here about the space taken up by the inputs.

it’s very obvious that when the size of the input grows n grows as well and the space taken up in the memory grows also.

I’m talking about the space taken up by the algorithm only (the code you type), not including the inputs.

It’s also called Auxiliary Space Complexity.

Rules of thumb

Constant Space Complexity O(1)

Most Primitives

• Booleans
• numbers
• undefined
• null

Linear Space Complexity O(n)

• Strings
• Arrays
• Objects

Examples

function arrSum(arr) {
  let sum = 0;

  for (let i = 0; i < arr.length; i++) {
    sum += arr[i];
  }

  return sum;
}

Spaces taken are:

• 1 number => let sum = 0.

• 1 number => let i = 0.

• So the equation will be O = 1 + 1 so its O(1).
  

function makeDouble(arr) {
  let myArr = [];

  for (let i = 0; i < arr.length; i++) {
    arr.push(2 * arr[i]);
  }

  return myArr;
}

Spaces taken are:

• 1 number => let i = 0.

n number (return myArr) since the returned array depends on the length of the given array.

So the equation will be O = 1 + n so its O(n).

I know that I said earlier that we will ignore the size of the inputs but here in this example my created and returned array (the code I typed) will be affected by the length of the given array so the space taken up for this array will increase by n.

Summary

In conclusion, Big O Notation helps us efficiently type code that runs as quickly as possible and less memory-intensive as possible.

Resources

JavaScript Algorithms and Data Structures Masterclass

Introduction to Big O Notation and Time Complexity