Overview

This post summarizes the foundational knowledge of calculating algorithm performance using Big O notation and complexity.

What is Complexity (Order)?

• A metric that represents the rate at which execution time increases as data volume increases.
  • Time Complexity
    • Processing time
  • Space Complexity
    • Memory usage

Big O/Big θ/Big Ω

These notations describe computation time, but here we summarize their academic differences.

• Big O
  • Upper bound of computation time
• Big θ
  • Lower bound of computation time
• Big Ω
  • Both O and Ω

Best/Worst/Average Case

A summary of the three patterns representing algorithm execution time.

• Best Case
  • The lower bound of complexity. A case where all element values are equal. It is rarely discussed as it is often executable in O(₁) and significantly differs from the worst or average case.
• Worst Case
  • The upper bound of complexity.
• Average Case
  • The average complexity. A case where element values are average.

In many algorithms, the worst case and average case often coincide.

Big O Notation

Representative notations are summarized in order of shortest processing time.

How to Determine Complexity

Calculate the number of steps and determine complexity based on their sum. When determining complexity, the following two points are of low importance and can be omitted.

• Omit non-maximum degree terms
  • O(n²+n)
    • Consider as O(n²)
• Omit coefficients
  • O(2n)
    • Consider as O(n)

Whether to add or multiply execution times in step calculations depends on whether the processes occur simultaneously or not.

If they do not occur simultaneously, add execution times.

for (condition) {
  // do something
}

for (condition) {
  // do something
}

If they occur simultaneously, multiply execution times.

for (condition) {
  for (condition) {
    // do something
  }
}

Examples

Linear Search

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

for (let i = 0; i < data.length; i++) {
	if (targetData == data[i]) {
  	console.log(`${i}番目でデータを発見した`); // Executed data.length times → n times
    return;
  }
}

console.log('目的のデータはない'); // Executed once

In the above code, the total number of steps is 1+1+n+1=3n. Excluding coefficients, the complexity is O(n).

Nested for Loop

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

for (let i = 0; i < data.length; i++) {
	console.log(`${i}回目の処理`); // Executed once
	for (let j = 0; j < data.length; j++) {
		console.log(j); // Executed 4 * 4 times → n² times
  }
}

In this case, the number of steps is 1+1+n²=2n², so excluding coefficients, the complexity is O(n²).

Algorithms with Logarithmic Complexity

const n = 10;  // Executed once

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

When n is 1 Loop count 1

When n is 4 Loop count 2

When n is 8 Loop count 3

The loop count is determined by log2ⁿ. The number of steps is 1+log2ⁿ, so excluding various factors, the complexity is log n.

Reference Links

• About Complexity Order
• [For Beginners] How to Determine Program Complexity
• [For Beginners] How to Determine Program Complexity
• Comprehensive Guide to Determining Complexity Order! ~ Where Does log Come From ~
• techscore - A Basic Guide to Algorithms and Complexity for New Developers

Reference Books

• Cracking the Coding Interview: 189 Programming Questions and Solutions
  • Easy-to-understand examples about Big O notation.
• Algorithm Picture Book: 26 Algorithms Explained with Pictures
• Algorithms and Data Structures for Programming Contests
• Let's Start with Algorithms
• Web+DB Press vol.91 2016