Question $1(10$ points$)$: Give short but formal proofs of the following:

$($a$)f(n)=6n-{10}^{14}$ is $O(n),$ but $f(n)=2^{2n-2}$ is not $O(2^n)$

$($b$)f(n)=O(g(n)),$ where $f(n)=19n+15$ and $g(n)=n^2-50n.$

Question $2(10$ points$)$: Consider the following algorithm, which takes as input an array $A$ :

What is the asymptotic running time of PrintThings$($A$)$ if the length of $A$ is $n?$

We expect: an answer like "The running time of PrintThings$($A$)$ is $O(dots)"$ with a short

explanation.

Question $3(10$ points$)$: Find an optimal parenthesization of the following matrix$-$chain product:

$A_{32}{A}_{28}{A}_{81}{A}_{15}$