Asymptotic Notation

This note is part of my learning notes on Data Structures & Algorithms.

---

Asymptotic Notation

Asymptotic notations are mathematical notations used to describe the limiting behavior of a function as its argument approaches infinity or some other limiting value. They are commonly used to analyze the time complexity (time required) or space complexity (memory required) of algorithms. They are also convenient for describing the worst-case running-time function $T(n)$.

Big O Notation

Big O notation describes an upper bound on the time complexity of an algorithm. It provides an asymptotic upper limit for the growth rate of a function as the input size approaches infinity.(worst case)

A function $f(n)$ is $O(g(n))$ if there exist positive constants $c$ and $n_0$ such that for all $n \geq n_0$ ,

$$f(n) \leq c \cdot g(n)$$

Big Omega Notation $(\Omega)$

Big Omega notation describes a lower bound on the time complexity of an algorithm. It provides an asymptotic lower limit for the growth rate of a function as the input size approaches infinity. (best case)

A function $f(n)$ is $\Omega(g(n))$ if there exist positive constants $c$ and $n_0$ such that for all $n \geq n_0$ ,

$$f(n) \geq c \cdot g(n)$$

Big Theta Notation $(\theta)$

Big Theta notation describes a tight bound on the time complexity of an algorithm. It provides an asymptotic tight limit for the growth rate of a function as the input size approaches infinity. (average case)

A function $f(n)$ is $\theta(g(n))$ if and only if $f(n)$ is both $O(g(n))$ and $\Omega(g(n))$ . That is, there exist positive constants $c_1$, $c_2$ and $n_0$ such that for all $n \geq n_0$ ,

$$c_1 \cdot g(n) \leq f(n) \leq c_2 \cdot g(n)$$

Visual Representations

---

Example 1.

Given a function $f(n) = 3n^2 + 5n+2$ , prove that $f(n)$ is $O(n^2)$.

Find constants $c$ and $n_0$ such that for all $n \geq n_0$ ,

$$f(n) \leq c \cdot n^2$$

We can choose $c=10$ and $n_0=1$ after inspecting the function.
For $n \geq 1$

$$3n^2 + 5n +2 \leq 3n^2 + 5n^2 + 2n^2 = 10n^2$$

Hence, $f(n)$ is $O(n^2)$ with $c=10$ and $n_0 = 1$.

Example 2.

Given the function $h(n) = 7n^2 + 3n-5$, prove that $h(n)$ is $\theta(n^2)$.

Find constants $c_1, c_2$ and $n_0$ such that for all $n \geq n_0$ ,

$$c_1 \cdot n^2 \leq 7n^2 + 3n -5 \leq c_2 \cdot n^2$$

We can choose $c_1 = 6, c_2=8$ and $n_0=1$ after inspecting the function.
For $n \geq 1$

$$6n^2 \leq 7n^2 + 3n-5 \leq 8n^2$$

Hence, $h(n)$ is $\theta(n^2)$ with $c_1 = 6, c_2=8$ and $n_0=1$ .

---

References

• Animated tutorial of Asymptotic Notation