dark

# How to calculate big o notation ?

## What is Big O Notation ?

Big O notation is a mathematical notation that describes the limiting behavior of a function when the argument tends towards a particular value or infinity. src

## What is Time Complexity ?

Time complexity is defined as the amount of time taken by an algorithm to run, as a function of the length of the input.

You can check out the different complexity times in the table below:

Time Complexity Name Complexity
Constant O(1)
Linear O(n)
Logarithmic O(log n)
Exponential O(2^n)
Factorial O(n!)

You can see the big o notation of common functions here.

To get a good perspective of time complexities, we can use the graphical calculator of these constants. You can use desmos graph calculator. I created a simple demo, you can check out here.

By calculating time complexity of an algorithm, we can get an information about scalability and performance. If we have an algorithm that performs in quadratic or exponential time complexity, we can try to optimize it, so it can scale.

You can see some examples of time complexities of loops.

``````//O(n)
for(let i=0; i<n; i++){

}

//O(n*m) --> O(n²)
for(let i=0; i<n; i++){
for(let j=0; j<m; j++){

}
}

let s = 0; //O(1)

//O(log(n))
for(let i=n; i>0; i=i/2){

}

``````

When we check out the graph examples in the desmos calculator, we get a better picture of how algorithms can scale. And this is not related to the only algorithms, we can use this knowledge for database queries. For example, if we have a table with no index defined, the time complexity for search will be O(n). But if we define an index, the time complexity of search will be O(log(n)). Because when we create an index, we don’t have to check every row in the table; instead, we can use a divide-and-conquer algorithm by looking based on index.

## Calculation

Let’s see how can we calculate big o notation of an algorithm.

``````
let sum = (n) => {
let res = 0 // O(1)
for(let i=0; i<n; i++){ //O(n)
res += i // O(1)
}
return res // O(1)
}
``````

So when we sum all time complexity, we get O(n).

``````sum = 1 + n*1 + 1 = n + 2 => O(n)
``````

An example for `n*log(n)` time complexity

``````
let sumDivide = (n) => {
let res = 0 // O(1)
for(let i=n; i<n; i/2){ //O(log(n))
for(let j=n; j<n; j/2){ //O(n)
res += j // O(1)
}
}
return res // O(1)
}
``````
``````sumDivide = 1 + log(n)*n*1 + 1 = n*log(n) + 2 => O(n*log(n))
``````
##### Previous Post ## Detecting intrusion in DevOps environments with AWS canary tokens

##### Next Post ## Best programming co pilot?

##### Related Posts ## The Day-1 Decisions that Make or Break Companies w/ PlanetScale’s CEO Sam Lambert

Your early tech stack decisions won’t ensure long term success, but they can certainly set you up for … Read more ## The Science Of Allocating Dev Resources In 2023

The days of growth at all costs are over; your 2023 engineering strategy needs to be about scaling … Read more ## Paso a paso: Cómo mejorar la seguridad de tu aplicación frontend usando AWS Secret Manager, ejemplo con VueJs

Hoy vamos a tratar un tema que muchas veces pasamos por alto, la seguridad en aplicaciones frontend (aplicable … Read more