Algorithm Complexity

Author: Tatyana Milkina

Algorithm complexity is typically evaluated by execution time or memory usage.

Asymptotic complexity refers to the behavior of an algorithm as the input size approaches infinity. It is commonly represented using Big O notation. Examples include:

O(1) – constant time complexity
O(n) – linear time complexity
O(log n) – logarithmic time complexity
O(n*log(n)) – quasilinear time complexity
O(n²) – quadratic time complexity
O(2ⁿ) – exponential time complexity

Algorithm complexity graph

Growth rate chart

Rules for using Big O notation:

Constants are ignored. For example:

8n⁴ = O(n⁴)

(n²)/5 = O(n²)
Only the term with the fastest growth rate matters because, for large n, other terms become insignificant:

n² + n = O(n²)

2ⁿ + n⁹ = O(2ⁿ)
The base of logarithms is omitted, as they differ only by a constant factor: O(log n).

Курс 'Java для начинающих' на Udemy