Complexity Analysis

Computational complexity is designed to compare two or more algorithms, independently of computer hardware capabilities and coding language.

Asymptotic Notation §

There are three ways of measuring complexity asymptotically:

1. Big-O Notation: Measures the worst-case complexity, the limit of an algorithm
2. Big-Theta: Measures the average-case complexity, can be thought of as the between area between worst-case and best-case
3. Big-Omega: Measures the best-case complexity, namely is considered the base of the algorithm.

Example: $8n^2+2^n+3=O(2^n)$ , because $2^n$ increases the most as n approaches infinity

Big-O Notation $O(n)$ §

Big-Theta Notation $\Theta (n)$ §

This is used to measure the average-case complexity of an algorithm/function/operation.

Big-Omega Notation $\Omega (n)$ §

This is used to measure the best-case complexity of an algorithm/function/operation. It is considered the floor for the growth function

Example: In a linear search for an array of size n, the best-case would be that the term is in the first index, 0. This means only 1 operation is needed. Therefore the big-omega would be $\Omega (1)$

Growth Functions - $f(n)$ and $g(n)$ §

Most algorithms’ time complexities are represented by $f(n)$. For example, Mergesort has an $f(n)=n\log (n)$ (Note, $f(n)$ does NOT contain big-O).

---

• Big-O Notation
• Computational Limits
• Master Theorem
• Space Complexity
• Time Complexity

---