Big-O Notation and Calculation

--

Algorithm performance depends on the input size and the number of operations it executes. We, the software engineer, have to analyze the performance worst case according to time-space tradeoff.

O-Notation helps us analyze the worst case a.k.a. the upper bound of algorithm performance in terms of time complexity and space complexity.

1. Common O-Notation from worst to best
2. O-Notation of time complexity from worst to best
3. O-Notation of space complexity from worst to best
4. Procedure to calculate complexity

1. Common O-Notation from worst to best

1. Factorial — O(n!)
2. Exponential — O(c^n)
3. Polynomial — O(n^c)
4. Superlinear — O(n log n)
5. Linear — O(n)
6. Logarithmic — O(log(n))
7. Constant O(1)

1.1 Mathematic Examples

`if n = 20:1. Factorial -> 20! = 2.432902e+12. Exponential -> 220 = 10485763. Polynomial -> 202 = 4004. Superlinear -> 20 log20 = 59.95. Linear -> 20 = 206. Logarithmic -> log20 = 27. Constant -> 1 = 1`

2. O-Notation of time complexity from worst to best

1. O(n!) — Factorial Algorithm : brute force algorithm for Traveling Salesman Problem
2. O(c^n) — Exponential Algorithm : tower of hanoi
3. O(n^c) — Polynomial Algorithm : bubble sort, selection sort, insertion sort, bucket sort
4. O(n log n) — Superlinear Algorithm : heap sort, merge sort
5. O(n) — Linear Algorithm : linear search
6. O(log n) — Logarithmic Algorithm : binary search
7. O(1) — Constant Algorithm : ideal

3. O-Notation of space complexity from worst to best

1. O(n+k) — Sub-linear Algorithm : radix sort
2. O(n) — Linear Algorithm : quick sort
3. O(log n) — Logarithmic Algorithm : merge sort
4. O(1) — Constant Algorithm : linear search, binary search, bubble sort, selection sort, insertion sort, heap sort, shell sort

4. Procedure to calculate complexity

1. Figure out the input.
2. Figure out n — input size / max. number of operations.
3. Express the performance function of algorithm in terms of n
4. Pay attention only to higher order terms of equation.
5. Erase constant factor.

4.1 Procedure Example

1. Constant Multiplication — if f(n) = c.g(n), then O(f(n)) = O(g(n))
2. Polynomial Function — if f(n) = a_0 + a_1.n + a_2.n² + … + a_m.n^m, then O(f(n)) = O(nm)
3. Logarithmic Function — if f(n) = log_a n and g(n) = log_b n, then O(f(n)) = O(g(n))
4. Summation Function — if f(n) = f_1(n) + f_2(n) + … + f_m(n) and f_i(n) <= f_(i+1)(n) for all i = 1,2,…,m, then O(f(n)) = max(f_1(n), f_2(n), …, f_m(n))

References:

--

--

Write about software engineering and career