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)\text{ whenever }n\geq n_0

let t(n) = 100n + 6

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

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

101n <= 101 (whenever n >= 1)

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

why did we take n >= 1

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

100n + 6 O()

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

100n <= 101 whenever n >= 1

Big Notation

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

then:

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

example:

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_1g(n)\leq t(n)\leq C_2g(n)\text{ whenever }n\leq n_0

example:

t\left(n\right)=\frac{n}{2}\left(n-1\right)\text{ or }\frac{n^2}{2}\text{ whenever }n\geq2

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

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

Inequality no 1

\boxed{=\frac{n}{2}\left(n-1\right)\quad\geq\quad\frac{1}{4}\cdot n^2\text{ whenever }n\geq2}

Again

	Whenever
	Whenever

Inequality no 2

Whenever

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

tn\quad\varepsilon\quad\theta{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\Theta(g_1(n))\quad\text{and}\quad t_2(n)\in O(g_2\left(n)\right)

then

t_1(n)+t_2(n)\in\Theta\big(\max(g_1n,g_2n)\big).

Proof

We know that

t_1(n)\in O(g_1(n))\quad\implies\quad t_1(n)\leq c_1g_1(n),\quad\forall n\geq n_1,

and

t_2(n)\in O(g_2(n))\quad\implies\quad t_2(n)\leq c_2g_2(n),\quad\forall n\geq n_2

Let

Then, for all , inequalities (1) and (2) hold simultaneously.

Thus,

t_1(n)+t_2(n)\;\;\leq\;\;c_1g_1(n)+c_2g_2\left(n\right)

Now, observe that

c_1g_1(n)+c_2g_2(n)\;\;\leq\;\;(c_1+c_2)\,\max(g_1n,g_2n))

Therefore,

t_1(n)+t_2\left(n)\in O\big(\max(g_1n,g_2n)\big)\right.

Since , we also know there exists a constant such that

t_1(n)\geq kg_1(n),\quad\forall n\geq n_1

This implies that for sufficiently large ,

t_1(n)+t_2(n)\;\;\geq\;\;kg_1(n).

Hence,

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

t_1(n)+t_2\left(n)\in\Theta\big(\max(g_1n,g_2n)\big).\right.\quad\left(4\right)

✅ Hence proved

Theorem 2

t_1(n)\in\Theta(g_1(n))\quad\text{and}\quad t_2(n)\in O(g_2\left(n)\right)

then

t_1(n)\cdot t_2(n)\in O\big(\max(g_1n,g_2n)\big))

Proof

We have

t_1(n)\in O(g_1(n))\quad\implies\quad t_1(n)\leq c_1\,g_1(n),\quad\text{whenever }n\geq n_1

and

t_2(n)\in O(g_2(n))\quad\implies\quad t_2(n)\leq c_2\,g_2(n),\quad\text{whenever }n\geq n_2\quad\left(2\right)

Let

n_0=\max(n_1,n_2)

Then, for all , both inequalities (1) and (2) hold.

Multiplying (1) and (2):

t_1(n)\cdot t_2(n)\;\;\leq\;\;c_1c_2\,g_1(n)g_2(n),\quad\forall n\geq n_0

Thus,

t_1(n)\cdot t_2(n)\in O(g_1(n)g_2\left(n)\right)

✅ Hence proved

find the Big O estimation of n! and

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

;

Asymtotic Notation

Big O Notation

Big Notation

Theta Notation

Note

Theorem 1

Proof

Theorem 2

Proof

find the Big O estimation of n! and

Taking log both side