$1$ Theory

Do the following problems. Submit a PDF $($not a scan of hand$-$written work$)$ called hw$1.$pdf $.$

For the following problems, use the definition of Big$-$Oh$,$ as given on pg$.17$ of the text, and in class, and the weaker definition of Big$-$Omega, on pg$.18$ of the text:

$T(n)in(f(n))>EEcin{Z}^{+}s.t.f(n)cT(n)$ infinitely often.

to support the following statements. If the statement can't be supported by the definition, show this.

Let $T(n)=3n^3+5n^2\sqrt[\phantom{2}]{n}+17n\sqrt[\phantom{2}]{n}+12\sqrt[\phantom{2}]{n}$

a$.$ Show that $T(n)inO(n^3)$

b$.$ Show that $T(n)in(n^3)$

Let $T(n)=8n^{2}sinn+42$

a$.$ Show that $T(n)inO(n^2)$

b$.$ Show that $T(n)in(n^2)$

Show that $5n^3+17$inO$(n)$

Ex$.1\mathrm{.}10$ from text. You needn't compare $f_i$ to $f_i,$AAi. Show your reasoning.

Given your results from the previous exercise, by the definitions given on ppg $17$ and $18,$ does finO$(g)Longrightarrowgin(f)?$ Support your answer $.$

Ex$.1\mathrm{.}12$ from text

Note the formatting error in part $b.$ The $j-$loop is in the body of the $i-$loop.

For part d$,$ set up the recurrence relation. Then take a stab at solving it using repeated substitution $($there is an example in the chapter$),$ or use Maple, Matlab, etc to solve it$.$