Asymtotic Notation

Abhijeet Singh Rajput

@abhijeetsingh

Created

Jul 29, 2025

Last Modified

2 weeks ago

Asymtotic Notation

Asymtot is a barier blockage which stop the ...

Asymtotic notation are used to categorise the function on the basis of their growth.

There are 3 main category of Asymtotic notation

Big O Notation

Let t(n) and g(n) are two positive functions then

t(n) is said to be in O{g(n)} if:

t(n) is bounded above by some positive constant multiple of g(n) for large values of n

t (n) \leq C \cdot g (n) whenever n \geq n_{0}

let t(n) = 100n + 6

100n + 6 <= 100n + n, (n >= 6)

100n + 6 <= 101n (n >= 6)

101n <= 101 $n^{2}$ (whenever n >= 1)

100n + 6 <= 101 $n^{2}$ (whenever n >= 6)

why did we take n >= 1

100n + 6 <= 101 $n^{2}$ whenever n >= 6

100n + 6 $ϵ$ O( $n^{2}$ )

100n + 6 <= 101n whenever n>=6

100n <= 101 $n^{2}$ whenever n >= 1

Big $Ω$ Notation

let t(n) and g(n) are two positive function

then:

t(n) is said to be in $Ω (g (n))$ if t(n) is bounded bellow by some positive constant of g(n) multiple of g(n) for large values of n

$c \cdot g (n) \leq t (n) whenever n \geq n_{o}$

$t (n) ϵ Ω (g (n))$

example:

$t (n) = n^{3}$

$1 n^{2} \leq n^{3} whenever n \geq 1$

Theta $Θ$ Notation

let t(n) and g(n) are two positive function then t(n) is said to be in $θ$ {g(n)} if

t(n) is bounded above and bounded below by some positive constant multiple of g(n) for large values of n

i.e.

C_{1} g (n) \leq t (n) \leq C_{2} g (n) whenever n \leq n_{0}

$t (n) ϵ θ (g (n))$ example:

t (n) = \frac{n}{2} (n - 1) or \frac{n ^{2}}{2} whenever n \geq 2

= \frac{n ^{2}}{2} - \frac{n}{2} \geq \frac{n ^{2}}{2} - \frac{n ^{2}}{4}

= \frac{n ^{2}}{2} - \frac{n}{2} \geq \frac{1}{4} \cdot n^{2} whenever n \geq 2

Inequality no 1

= \frac{n}{2} (n - 1) \geq \frac{1}{4} \cdot n^{2} whenever n \geq 2

Again

$\frac{n}{2} (n - 1) = \frac{n ^{2}}{2} - \frac{n}{2}$	Whenever $n \geq 0$
$\frac{n}{2} (n - 1) = \frac{n ^{2}}{2} - \frac{n}{2} \leq \frac{n ^{2}}{2}$	Whenever $n \geq 1$

Inequality no 2

\frac{n}{2} (n - 1) \leq \frac{1}{2} \cdot n^{2}

Whenever $n \geq 2$

In common reason both the equality will be valid simultaneously
thus we have

\frac{1}{4} \cdot n^{2} \leq \frac{n}{2} (n - 1) \leq \frac{1}{2} \cdot n^{2}

Theta notation example demonstrating c1·g(n) ≤ t(n) ≤ c2·g(n) with a quadratic bound, illustrating tight bound Θ(g(n)).

Note

t n ε θ g (n)

Big-O and Omega bounds illustration showing c1·g(n) ≤ t(n) ≤ c2·g(n), representing lower bound Ω(g(n)) and upper bound O(g(n)).

$⟺$ Bidirectional implication.

Theorem 1

t_{1} (n) \in Θ (g_{1} (n)) and t_{2} (n) \in O (g_{2} (n))

then

t_{1} (n) + t_{2} (n) \in Θ (max (g_{1} n, g_{2} n)) .

Proof

We know that

t_{1} (n) \in O (g_{1} (n)) ⟹ t_{1} (n) \leq c_{1} g_{1} (n), \forall n \geq n_{1},

and

t_{2} (n) \in O (g_{2} (n)) ⟹ t_{2} (n) \leq c_{2} g_{2} (n), \forall n \geq n_{2}

Let

$n_{0} = max (n_{1}, n_{2})$

Then, for all $n \geq n_{0}$ , inequalities (1) and (2) hold simultaneously.

Thus,

t_{1} (n) + t_{2} (n) \leq c_{1} g_{1} (n) + c_{2} g_{2} (n)

Now, observe that

c_{1} g_{1} (n) + c_{2} g_{2} (n) \leq (c_{1} + c_{2}) max (g_{1} n, g_{2} n))

Therefore,

t_{1} (n) + t_{2} (n) \in O (max (g_{1} n, g_{2} n))

Since $t_{1} (n) \in Θ (g_{1} (n))$ , we also know there exists a constant $k > 0$ such that

t_{1} (n) \geq k g_{1} (n), \forall n \geq n_{1}

This implies that for sufficiently large $n$ ,

t_{1} (n) + t_{2} (n) \geq k g_{1} (n) .

Hence,

$t_{1} (n) + t_{2} (n) \in Ω (max (g_{1} n, g_{2} n)) .. (4)$

From (3) and (4), we conclude:

t_{1} (n) + t_{2} (n) \in Θ (max (g_{1} n, g_{2} n)) . (4)

✅ Hence proved

Theorem 2

t_{1} (n) \in Θ (g_{1} (n)) and t_{2} (n) \in O (g_{2} (n))

then

t_{1} (n) \cdot t_{2} (n) \in O (max (g_{1} n, g_{2} n)))

Proof

We have

t_{1} (n) \in O (g_{1} (n)) ⟹ t_{1} (n) \leq c_{1} g_{1} (n), whenever n \geq n_{1}

and

t_{2} (n) \in O (g_{2} (n)) ⟹ t_{2} (n) \leq c_{2} g_{2} (n), whenever n \geq n_{2} (2)

Let

n_{0} = max (n_{1}, n_{2})

Then, for all $n \geq n_{0}$ , both inequalities (1) and (2) hold.

Multiplying (1) and (2):

t_{1} (n) \cdot t_{2} (n) \leq c_{1} c_{2} g_{1} (n) g_{2} (n), \forall n \geq n_{0}

Thus,

t_{1} (n) \cdot t_{2} (n) \in O (g_{1} (n) g_{2} (n))

✅ Hence proved

find the Big O estimation of n! and $lo g_{2} n!$

Step-by-step inequality showing n! ≤ nⁿ by bounding each factorial term with n, used to prove an asymptotic upper bound.

$n! \leq 1 \cdot n^{n} when n \geq 1$ ;

$n! ϵ O {n^{n}}$

Taking log both side

$lo g_{2} n! \leq 1 \cdot lo g_{2} n^{n} when n \geq 1$

$l o g_{2} n! \leq 1 \cdot n lo g_{2} n when n \geq 1$

$lo g_{2} n! ϵ O (n lo g_{2} n)$

Asymtotic Notation

Asymtotic Notation

Big O Notation

Big Ω Notation

Theta Θ Notation

Note

Theorem 1

Proof

Theorem 2

Proof

find the Big O estimation of n! and log2​n!

Taking log both side

Big $Ω$ Notation

Theta $Θ$ Notation

find the Big O estimation of n! and $lo g_{2} n!$