Asymptotic Notation

Algorithms-1

• Asymptotic Notation:
  • [Manual Method](#hard\ method)
  • O, theta, omega, notation
  • examples?

---

Hard Method

Insertion Sort (A)	cost	times
for j = 2 to A.length	$c_1$	$n$
key = A[j]	$c_2$	$n-1$
i = j - 1	$c_3$	$n-1$
while i > 0 && A[i] > key	$c_4$	${\sum }_{j=2}^n{t}_j$
A[i+1] = A[i]	$c_5$	${\sum }_{j=2}^n(t_j-1)$
i = i - 1	$c_6$	${\sum }_{j=2}^n(t_j-1)$
A[i+1] = key	$c_7$	$n-1$

$t_j$ is the number of times the while loop repeats for every value of j

Total Cost: $\sum cost\ast time$

$$T(n)=c_{1}n+c_2(n-1)+c_3(n-2)+c_4\sum _{j=2}^n{t}_j+c_5\sum _{j=2}^n(t_j-1)+c_6\sum _{j=2}^n(t_j-1)+c_7(n-1)$$

Then analyse

• best case
  • $t_j=1\forall j$
• and worst case possibilities
  • $t_j=j\forall j$

Finally express $T(n)$ in the most general form you can e.g. as a quadratic $a{n}^2+bn+c$ you can then say $T(n)$ is a quadratic function of $n$

---

$O(n),\Theta (n),\Omega (n)$ Notation

$\Theta (g(n))=\{f(n):\exists c_1,c_2,n_0\in Z^{+},\text{ such that }0\le c_{1}g(n)\le f(n)\le c_{2}g(n)\forall n\ge n_0\}$

$O(g(n))=\{f(n):\exists c_1,n_0\in Z^{+},\text{ such that }0\le f(n)\le c_{1}g(n)\forall n\ge n_0\}$

$\Omega (g(n))=\{f(n):\exists c_1,n_0\in Z^{+},\text{ such that }0\le c_{1}g(n)\le f(n)\forall n\ge n_0\}$

in equality and inequalities

$2n^2+3n+1=2n^2+\Theta (n)=\Theta (n^2)$

comparing functions

1. $f(n)=\Theta (g(n))$ and $g(n)=\Theta (h(n))$ implies $f(n)=\Theta (h(n))$
   1. this is true for $O$ and $\Omega$ as well
2. $f(n)=\Theta (f(n))$
   1. also true for $O$ and $\Omega$

Standard Functions

Polynomials

asymptotically positive polynomial ($a_d>0$) $⟹$ $p(n)=\Theta (n^d)$

exponential

$|x|<1⟹e^x=\Theta (n^2)$

---

Examples

2024MA

$Q1$

$$T(n)=3T(n/4)+n\log n$$

$Q2$

$$T(n)=\{\begin{array}{ll}2& n\le 2\\ \sqrt{n}T(\sqrt{n})+\sqrt{n}& n>2\end{array}$$