## DEV Community is a community of 862,249 amazing developers

We're a place where coders share, stay up-to-date and grow their careers. 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. ``````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;
}
``````

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) => {

/* 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){
}
}

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

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

//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) => {

/*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++){
}
}

/*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?