DEV Community

Cover image for The Big O Notation | Quadratic, constant and linear calculations in javascript
Luiz Calaça
Luiz Calaça

Posted on • Updated on

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.

Constant Time- Geogebra

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

const tripleNumber(number) => {
   return number number*3;
}
Enter fullscreen mode Exit fullscreen mode

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.

Linear Time - Geogebra

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

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

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).

Quadratic Time - Geogebra

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])
     }
   }
}
Enter fullscreen mode Exit fullscreen mode

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!')
   }
}
Enter fullscreen mode Exit fullscreen mode

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))
Enter fullscreen mode Exit fullscreen mode

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
     }
}
Enter fullscreen mode Exit fullscreen mode

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

Any doubt?

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

Contacts
Email: luizcalaca@gmail.com
Instagram: https://www.instagram.com/luizcalaca
Linkedin: https://www.linkedin.com/in/luizcalaca/
Twitter: https://twitter.com/luizcalaca

Discussion (0)