Complexity of an Algorithm and Asymptotic Notations

Complexity of an algorithm is a measure of the amount of time and/or space (memory) required by an algorithm as a function of the input size $n$.

---

What is Algorithm Complexity?

Algorithm complexity describes how the resource usage (time or space) of an algorithm grows as the input size increases. It helps us compare algorithms and choose the most efficient one.

• Time Complexity — the number of basic operations performed as a function of input size $n$
• Space Complexity — the amount of memory used as a function of input size $n$

We express complexity using asymptotic notations, which describe the behavior of a function for large values of $n$ (i.e., as $n \to \infty$).

---

Asymptotic Notations

There are three main asymptotic notations:

---

A. Big-O Notation (O) — Upper Bound

Big-O gives the worst-case (upper bound) of an algorithm's growth rate.

Definition: A function $f(n) = O(g(n))$ if there exist positive constants $c$ and $n_0$ such that:

$$f(n) \leq c \cdot g(n) \quad \text{for all } n \geq n_0$$

Geometrical Interpretation: The graph of $f(n)$ lies on or below the graph of $c \cdot g(n)$ for all values beyond $n_0$. It acts as a ceiling on the growth.

Example: If $f(n) = 3n + 2$, then $f(n) = O(n)$ because for $c = 4$ and $n_0 = 2$: $3n + 2 \leq 4n$ for all $n \geq 2$

---

B. Big-Omega Notation (Ω) — Lower Bound

Big-Omega gives the best-case (lower bound) of an algorithm's growth rate.

Definition: A function $f(n) = \Omega(g(n))$ if there exist positive constants $c$ and $n_0$ such that:

$$f(n) \geq c \cdot g(n) \quad \text{for all } n \geq n_0$$

Geometrical Interpretation: The graph of $f(n)$ lies on or above the graph of $c \cdot g(n)$ for all values beyond $n_0$. It acts as a floor on the growth.

Example: If $f(n) = 3n + 2$, then $f(n) = \Omega(n)$ because for $c = 3$ and $n_0 = 1$: $3n + 2 \geq 3n$ for all $n \geq 1$

---

C. Big-Theta Notation (Θ) — Tight Bound

Big-Theta gives the exact/tight bound — the function grows at the same rate as $g(n)$.

Definition: A function $f(n) = \Theta(g(n))$ if there exist positive constants $c_1$, $c_2$, and $n_0$ such that:

$$c_1 \cdot g(n) \leq f(n) \leq c_2 \cdot g(n) \quad \text{for all } n \geq n_0$$

Geometrical Interpretation: The graph of $f(n)$ is sandwiched between $c_1 \cdot g(n)$ and $c_2 \cdot g(n)$ for all values beyond $n_0$. The function is bounded both above and below.

Example: If $f(n) = 3n + 2$, then $f(n) = \Theta(n)$ because for $c_1 = 3$, $c_2 = 4$, and $n_0 = 2$: $3n \leq 3n + 2 \leq 4n$ for all $n \geq 2$

---

Summary Table

Notation	Bound Type	Meaning	Symbol
$O(g(n))$	Upper Bound	$f(n) \leq c \cdot g(n)$	Ceiling
$\Omega(g(n))$	Lower Bound	$f(n) \geq c \cdot g(n)$	Floor
$\Theta(g(n))$	Tight Bound	$c_1 \cdot g(n) \leq f(n) \leq c_2 \cdot g(n)$	Sandwich

---

Geometrical Diagram

Imagine a graph with $n$ on the x-axis and $f(n)$ on the y-axis:

---

Conclusion

Asymptotic notations provide a mathematical framework to classify algorithms based on their efficiency. Big-O is most commonly used in practice to describe worst-case performance, while Big-Theta gives the most precise characterization of an algorithm's complexity.