The Big O Notation | Quadratic, constant and linear calculations in javascript
Tags: math, bigo, computerscience, algorithms
Published: 2022-01-22 14:38:02

## **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)

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.

![Linear Time - Geogebra](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/3rvbclp0f89enr45us4y.png)

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

![Quadratic Time - Geogebra](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/wxqspczl7xevc8krue2s.png)

```
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](https://jsfiddle.net/luizcalaca/ojze04cq/7/), 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: luizcalaca@gmail.com
Instagram: https://www.instagram.com/luizcalaca
Linkedin: https://www.linkedin.com/in/luizcalaca/
Twitter: https://twitter.com/luizcalaca