Asymptotic notations

Exercise sheet

Exercise $1$:

Assume that each of the expressions below gives the processing time $T(n)$ spent by an algorithm for solving a problem of size $n.$ Select the dominant term$($s$)$ having the steepest increase in $n$ and specify the Big$-$Oh complexity of each algorithm.

$\backslash$table$[[$Expression$,$Dominant term,O$-$notation$],[5+0\mathrm{.}001n^3+0\mathrm{.}025n,,],[500n+100n^{1\mathrm{.}5}+50nlo{g}_{10}n,,],[0\mathrm{.}3n+5n^{1\mathrm{.}5}+2\mathrm{.}5n^{1\mathrm{.}75},,],[n^{2}lo{g}_{2}n+n(lo{g}_{2}n{)}^2,,],[nlo{g}_{3}n+nlo{g}_{2}n,,],[3lo{g}_{8}n+lo{g}_{2}lo{g}_{2}lo{g}_{2}n,,],[100n+0\mathrm{.}01n^2,,],[0\mathrm{.}01n+100n^2,,],[2n+n^{0\mathrm{.}5}+0\mathrm{.}5n^{1\mathrm{.}25},,],[0\mathrm{.}01nlo{g}_{2}n+n(lo{g}_{2}n{)}^2,,],[100nlo{g}_{3}n+n^3+100n,,],[0\mathrm{.}003lo{g}_{4}n+lo{g}_{2}lo{g}_{2}n,,]]$

Exercise $2$:

a$.$ Given any two functions $f(*)$ and $g(*),$ show that $f(n)+g(n)=(max\{f(n),g(n)\})$

b$.$ Decide whether these statements are True or False. You must briefly justify all your answers to receive full credit.

$O(f+g)=O(f)+O(g)$

If $f(n)=O(g(n))$ and $g(n)=O(h(n)),$ then $h(n)=(f(n))$

$O(f$:$g)=O(f)*O(g)$

if $g(n)=(f(n))$ and $h(n)=(f(n))$ then $g=(h(n))$