Asymptotic Notations - PCCST303

KTU PYQ

KTU PYQ, 6 marks: "Describe different notations used to express the time complexity of an algorithm."

Asymptotic notation describes the growth of an algorithm's running time rather than its exact runtime. There are three standard notations, O, Ω, and Θ.

O: upper bound

$f(n) = O(g(n))$ iff there exist positive constants $c$ and $n_0$ such that $f(n) \le c \cdot g(n)$ for all $n \ge n_0$ .

For example, for f(n) = 2n + 3, taking c = 5 gives $2n + 3 \le 5n$ for all $n \ge 1$ , so f(n) = O(n).

Ω: lower bound

$f(n) = \Omega(g(n))$ iff there exist positive constants $c$ and $n_0$ such that $f(n) \ge c \cdot g(n)$ for all $n \ge n_0$ .

For example, for f(n) = 2n + 3, taking c = 1 gives $2n + 3 \ge n$ for all $n \ge 1$ , so f(n) = Ω(n).

Θ: tight bound

$f(n) = \Theta(g(n))$ iff there exist positive constants $c_1$ , $c_2$ , and $n_0$ such that $c_1 \cdot g(n) \le f(n) \le c_2 \cdot g(n)$ for all $n \ge n_0$ .

For example, for f(n) = 2n + 3, the O and Ω results above already give $1 \cdot n \le 2n + 3 \le 5 \cdot n$ for $n \ge 1$ , so f(n) = Θ(n) with $c_1 = 1$ , $c_2 = 5$ .

Key Idea

Covering all three notations, O, Ω, and Θ, with a clear definition, graph, and example for each, is what separates a full-marks answer from a partial one. See the Asymptotic Notations lesson for the strict variants o() and ω().