Q$2$: A$)$ Use Compiler $($in: $C++)$ to create array $A=[dots..n],$

Generate A randomly as follows, then apply insertion and

selection sort for the same generated array:

$A=[1$dots..$n]$ Insertion sort time Selection sort time

B$)$ Apply insertion sort to sort the string "algorithm" in alphabetical

order

Show each iteration of insertion sort on the string. Find the number

of comparisons

Q$3$: Prove or disprove

$1.5n^2+40n+100=O(n^2).$

$2.\frac{n^3}{1000}=O(n^2).$

$3.f(n)={\displaystyle \underset{i=1}{\overset{n}{}}}i2.isf(n)=\frac{O}{n^3}?$

$4.n^k=\frac{O}{2^n}$

$5.{\displaystyle \underset{i=1}{\overset{n}{}}}logi=\frac{O}{nlogn}$

$6.7^n=(9^n)$

Q$4$: In each of the following situations, indicate whether $f=$

$O(g),$ or $f=(g),$ or both $f=\frac{O}{g}.$

$f(n)=n-100$ and $g(n)=n-200.$

$f(n)=n^{\frac{1}{2}}$ and $g(n)=n^{\frac{2}{3}}.$

$f(n)=100n+logn$ and $g(n)=n+(logn{)}^2.$

$f(n)=10logn$ and $g(n)=log(n^2).$

$f(n)=\frac{n^2}{logn}$ and $g(n)=n(logn{)}^2.$

$f(n)=n^{12}$ and $g(n)=4^{logn}$

$f(n)=n{2}^n$ and $g(n)=3^n.$

$f(n)=2^n$ and $g(n)=2^{n+1}.$

Q$5$: Find the complexity $($Exact and approximate$)$ for the

basic operations of the following algorithms:

sum $=0$;

for $(k=1$;$kn$;$k^{**}=2)$

for Q$5$: Find the complexity $($Exact and approximate$)$ for the

basic operations of the following algorithms:

sum $=0$;

for $(k=1$;$kn$;$k^{**}=2)$

for $(j=1$;$jn$;$++j)$

sum$++$;

${\displaystyle \underset{?}{\overset{?}{}}}2=0$;

for $(k=1$;$kn$;$k**=2)$

for $(j=1$;$jk$;$++j)$

sum$2++$;

int Fun$2($int n$)$

$\{$

if $(n0)$

return $1$ ;

for $($int $j=0$;$ji$;$j++nm(n0)$