Complexity.md

↥ back to Index

Table of Contents

• Complexity Analysis
  • Types
  • Logarithm
  • Order of Complexity from fastest to slowest
  • Complexity Chart

Complexity Analysis

The process of determining how efficient the algorithm is. Complexity analysis involves both Time and Space Complexities of an Algorithm.

It's needed to determine the better algorithm for the purpose.

Types

It is classified into 3 types.

1. Best Case - Big Omega
2. Medium Case - Big Theta
3. Worst Case - Big O

Logarithm

In Maths log means log₁₀, in Computer science log₂.

• log₂ 16 = ?; 2⁴ = 16; log₂ 16 = 4;

• log₂ 8 = ?; 2³ = 8; log₂ 8 = 3;

• log₂ 12 =?; 2³ = 8; 2⁴ = 16; log₂ 12 = 3.5

Order of Complexity from fastest to slowest

Very Important concept to understand before going deep inside Time and Space complexity.

1. Constant: O(1)
2. Logarithmic: O(log(n))
3. Linear: O(n)
4. Log-Linear: O(nlog(n))
5. Quadratic: O(n²)
6. Cubic: O(n³)
7. Exponential: O(2ⁿ)
8. Factorial: O(n!)

Complexity Chart