Asymptotic Running Time $[10$ points$]$

Consider the following running time functions, where $n>0.$

$3^n,n^3,\sqrt[\phantom{2}]{n},n^{2}log(n),nlog(n),n!,2^n,n^{2}log(n!)$

$n(n+1)-n^2,n+n^2,nlog(n^2),n^3-n^2,1,n^2-n,n^n,10,000$

$2^{nlo{g}_2(n)},nlo{g}_3(3n),2^{nlo{g}_2(3)},\frac{n^2}{log(n),\frac{n^{1\mathrm{.}5}}{n},n\sqrt[\phantom{2}]{n},nlo{g}_{10}(n),\frac{n^2}{100n}}$

a$.$ Identify groups of functions such that for any pair $(f(n),g(n))$ of functions in

the same group it holds that both $f(n)=O(g(n))$ and $g(n)=O(f(n)).$ Note

that some groups may contain a single function. $[7$ points$]$

Hint: For example, $f(n)=3n$ and $g(n)=n$ would be in the same group, as

$f(n)=3n=O(n)=O(g(n))$ and $g(n)=n=O(3n)=O(f(n)).$