How to Calculate Big O Notation?

Overview

• What is Big O Notation?
• What is Time Complexity?
• Calculation

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

Looking at graph examples in the Desmos calculator helps us understand how algorithms scale. This concept applies not only to algorithms but also to database queries. For instance, without an index on a table, a search operation will have a time complexity of O(n). With an index defined, the search time complexity improves to O(log(n)), allowing the use of a divide-and-conquer approach 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))