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

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).

Time Complexity §

Examples §

Command	Time complexity
Statements	$O(1)$ constant
Conditional statements	$O(1)$ constant
Loops	$O(n)$ linear
Nested loops	$O(n^c)$ polynomial
[[Divide-and-Conquer	Divide-and-Conquer]]

Link to source

Space Complexity §

Examples §

Command	Space complexity
Initializing, Assigning a variable	$O(1)$ constant
Storing an array/list/stack/queue	$O(n)$ linear
Iterative Function Calls	$O(1)$ constant
Recursive Function Calls	$O(n)$ linear

Link to source