DEV Community

Kenta Takeuchi
Kenta Takeuchi

Posted on • Originally published at bmf-tech.com

How to calculate O notation and algorithm complexity

Overview

This article is a translation of O(オーダー)記法とアルゴリズムの計算量の求め方
.
We will summarize the prerequisite knowledge about the O notation that roughly calculates the calculation performance of the algorithm and how to calculate the amount of calculation.

What is the amount of calculation (order)?

An index that expresses the calculation performance of the algorithm as the ratio of how much the execution time increases to the increase in the amount of data.

  • Time complexity
    • processing time
  • Spatial complexity
    • memory usage

Big O/Big θ/Big Ω

Each describes the calculation time, but summarizes the differences in academic meaning.

  • Big O
    • Upper limit of calculation time
  • Big θ
    • Lower limit of calculation time
  • Big Ω
    • Both O and Ω

Best/Worst/Expected Case

We will summarize the three patterns that represent the execution time of the algorithm.

  • Best case
    • Lower limit of computational complexity. The case where the values ​​of all elements are equal. There is not much discussion because the value is far from the worst case and the expected case, and it is usually the case that can be executed with O (₁).
  • Worst case
    • Upper limit of computational complexity.
  • Expected (average) case
    • Average amount of calculation. The case where the value of the element is average.

For many algorithms, the worst case and the expected case are often the same. It was

O notation

The representative ones are summarized in the order of the shortest processing time.

O notation Names in theory of computation Overview
O (₁) Constant time Processing time does not increase even if the amount of data increases
O (log n) Logarithmic time Calculation time hardly increases even if the amount of data increases. Even if it increases, the increase in the amount of calculation becomes smaller.
O (n) Linear time Processing time increases as the amount of data increases
O (n log n) Semi-linear, linear logarithmic time Slightly heavier than O (n)
O (n²) Squared time Processing such as checking all combination pairs from elements. As the amount of data increases, the amount of calculation increases.
O (n³) Polynomial Time Triple Loop
O (kⁿ) Exponential time Processing to get all combinations from elements
O (n!) Factorial time It takes time proportional to the factorial of n

How to calculate the amount of calculation

Calculate the number of steps and calculate the amount of calculation based on the total.
The following two points are of low importance when calculating the amount of calculation, so they are omitted.

  • Omit other than the maximum degree term
    • O (n² + n)
    • O (n²)
  • Omit the coefficient
    • O (2n)
    • O (n)

Whether to add or multiply the processing execution time in the step calculation depends on whether each processing occurs at the same time or not.

If it does not happen at the same time, add the execution time.

for (condition) {
  // do something
}

for (condition) {
  // do something
}
Enter fullscreen mode Exit fullscreen mode

If it happens at the same time, it takes time to execute.

for (condition) {
  for (condition) {
    // do something
  }
}
Enter fullscreen mode Exit fullscreen mode

example

Linear search

const targetData = 4; // Run once
const data = [1, 2, 3, 4, 5]; // Run once

for (let i = 0; i <data.length; i ++) {
if (targetData == data [i]) {
  console.log (`$ {i} th found data`); // data.length executed times → executed n times
    return;
  }
}

console.log ('No desired data'); // Run once
Enter fullscreen mode Exit fullscreen mode

In the case of the above code, the total number of steps is 1 + 1 + n + 1 = 3n.
Since the coefficient is excluded, the amount of calculation is O (n).

for statement dual structure

const data = [1, 2, 3, 4, 5]; // Run once

for (let i = 0; i <data.length; i ++) {
console.log (`$ {i} th process`); // Executed once
for (let j = 0; j <data.length; j ++) {
console.log (j); // 4 * Executed 4 times → Executed n² times
  }
}
Enter fullscreen mode Exit fullscreen mode

In the above case, the number of steps is 1 + 1 + n² = 2n², so the amount of calculation is O (n²) excluding the coefficient.

Algorithms whose computational complexity is logarithmic

const n = 10; // executed once

for (let i = 0; i <n; i = i * 2) {
  console.log (i ++); // log2 ⁿ Executed times
}
Enter fullscreen mode Exit fullscreen mode

When n is 1
Number of loops 1

When n is 4
Number of loops 2

When n is 8
Number of loops 3

The number of loops is calculated by log2ⁿ.
Since the number of steps is 1 + log2ⁿ, the amount of calculation is log n, omitting various things.

Reference link

Reference books

Top comments (0)