The Big O Notation | Quadratic, constant and linear calculations in javascript

What is Big O?

Big O notation help us for measuring the rate of growth of an algorithm and describes mathematically the complexity in the worst case. The measuring refers to number of operations it takes to complete the task.

The O is short for 'Order of'. So, if we’re discussing an algorithm with O(n^2), we say its order of, or rate of growth, is n^2, or quadratic complexity.

Let's see the constant, linear and quadratic and javascript examples.

O(1) — Constant Time

Given an input of size n, it only takes a single step for the algorithm to accomplish the task.

Examples: accessing and specific array index, pushing one element in array, insertion in queue.

https://dev-to-uploads.s3.amazonaws.com/uploads/articles/dhc1mritfulvvb7lr55x.png

const tripleNumber(number) => {
   return number number*3;
}

O(n) — Linear Time

Given an input of size n, the number of of steps required is directly related (1 to 1)

Examples: linear search and traversing and array.

fruits = ['banana', 'apple'];

const findApple = (array) => {
   for( let i=0; i < array.length ; i++){
      if(array[i] === 'apple')
        return true;
   }
  return false;
}

O(n²) — Quadratic Time

Given an input of size n, the number of steps it takes to accomplish a task is square of n.

Examples: bubble sort and traversing a matrix (2D array).

let matrix = [[0,1], [6,2]];

const getAllElementsMatrix = (matrix) => {
   for( let i=0; i < matrix.length ; i++){
     for( let j=0; j < matrix.length ; j++){
        console.log(matrix[i][j])
     }
   }
}

If we have more n elements, more operations we are going to do:

const large = new Array(1000000000).fill('apple');

const findApple = (array) => {
   for( let i=0; i < array.length ; i++){
      if(array[i] === 'apple'){}
        console.log('Apple here!')
   }
}

Try this, 1 billion os elements!

We can have a mix with this notations

Let's see an example in Javascript:

const numbers = [1,5,9,8]

const verifyAndReturn = (array) => {
    const someNumbers = []

        /* O(n) = O(4) because we have 4 elements 
        in the array */

    for( let i=0; i < array.length ; i++){ 
           if(array[i] % 2 == 0){
             someNumbers.push(array[i])
           }
        }

        /*O(1) because it iterate and get 
        the first element and returns it */

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

//The final will be O(4) + O(1) = O(5)

console.log(verifyAndReturn(numbers))

The final complexity as we can see in the code above will be O(4) + O(1) = O(5).

Let's see one more example:

const matrixNumbers = [[1,2], [3,5]]

const quadratic = (matrix) => {
      const someNumbers = []

      /*O(n^2) = O(2^2) because we have 2 sets 
      of elements in the matrix (4 elements)*/

      for( let i=0; i < matrix.length ; i++){ 
         for( let j=0; j < matrix.length ; j++){ 
            someNumbers.push(matrix[i][j])
         }
      }

     /*O(n) = O(4) because we have 4 elements 
     in the array from the before processing*/

     for( let i=0; i < someNumbers.length ; i++){
        //do Something
     }
}

The final complexity will be O(2^2) + O(4) = O(8).

Any doubt?

Important link: https://www.bigocheatsheet.com/

Contacts
Email: [e-mail]
Instagram: https://www.instagram.com/luizcalaca
Linkedin: https://www.linkedin.com/in/luizcalaca/
Twitter: https://twitter.com/luizcalaca