Question $1()$:

For each of the following functions, give the tightest upper bound chosen from among the usual

simple functions listed in Section $3\mathrm{.}5$ of the course readings. Answers should be expressed in big$-$O

notation.

$($a$)(1$ point$)f_2(n)=42n+9\sqrt[\phantom{2}]{n}+lo{g}_{2}n$

$($b$)(1$ point$)f_3(n)=4n^{0\mathrm{.}7}+6nlo{g}_{2}n+280$

$($c$)(1$ point$)f_1(n)=nlo{g}_{2}n+lo{g}_2{n}^2+280n$

Question $2()$:

Suppose the exact time required for an algorithm $A$ in both the best and worst cases is given by the

function

$T_A(n)=\frac{1}{280}{n}^2+42logn+12n^3+280\sqrt[\phantom{2}]{n}$

$($a$)(2$ points$)$ For each of the following statements, indicate whether the statement is true or false.

Algorithm A is $O(logn)$

Algoirthm $A$ is $O(n^2)$

Algoirthm $A$ is $O(n^3)$

Algoirthm $A$ is $O(2^n)$

$($b$)(1$ point$)$ Can the time complexity of this algorithm be expressed using big$-$ notation? If so$,$

what is it$?$

Question $3()$:

If possible, simplify the following expressions. Hint: See slide $11$ of topic $3$ of the lecture slides!

$($a$)(1$ point$)O(n^2)+O(logn)+O(nlogn)$

$($b$)(1$ point$)O(2^n)*O(n^2)$

$($c$)(1$ point$)42O(nlogn)+18O(n)$

$($d$)(1$ point$)O(n)+O(m),($yes$,$ that's an $\text{'}m\text{'},$ not a typo; note that $m$ is independent of $n)$