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 toward a particular value or infinity. Source

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:

You can see the Big O notation of common functions here.

To gain a better perspective on time complexities, we can use a graphical calculator for these constants. You can use the Desmos graph calculator. I created a simple demo; you can check it out here.

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

Here are 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 examine the graph examples in the Desmos calculator, we gain a clearer picture of how algorithms can scale. This knowledge is not limited to algorithms; we can also apply it to database queries. For example, if we have a table with no index defined, the time complexity for a search operation will be O(n). However, if we define an index, the time complexity for the search will be O(log(n)). This is because when we create an index, we do not need to check every row in the table; instead, we can utilize a divide-and-conquer algorithm based on the index.

Calculation

Let's see how we can calculate Big O notation for 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 complexities, we get O(n):

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

Here is an example of an O(n*log(n)) time complexity:

let sumDivide = (n) => {
  let res = 0 // O(1)
  for (let i = n; i > 0; i = i / 2) {
    // O(log(n))
    for (let j = n; j > 0; j = 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))