Problem $1.$

a$)$ Algorithm X uses $10nlogn$ operations, and algorithm Y uses $n^2$ operations. Determine the value of $n_0$ such that $x$ is faster than $Y$ for $n{n}_0.$

b$)$ Repeat part $($a$)$ assuming that Y uses $n$ sqrt$(n)$ operations

c$)$ Show that $2^{n+3}$ is $O(2^n)$ by finding the values of $n_0$ and $c$ such that $2^{n+3}c{2}^n$ for $n{n}_0.$ Explain why these values are correct.

NOTE: you may want to review logarithms and exponents first, in ch$.1$ of the textbook

d$)$ Show that $2^{3n}$ is not $O(2^n)$ by showing that such values of $n_0$ and $c$ do not exist. Alternately, you can do it by showing that for any positive constant $c,\underset{n}{lim}(\frac{2^{3n}}{2^n})>c$

Problem $2.$

a$)$ Order the following functions by the big$-O$ notation. If two functions are each is big$-O$ of the other, list them together.

$17nlogn,2^{17},loglogn,lo{g}^{17}n,2^{logn},sqrt(n),n^{0\mathrm{.}017},\frac{17}{n}$

$4n^{\frac{3}{2}},3n^{0\mathrm{.}5},17n,2nlo{g}^{2}n,2^n,nlo{g}_{17}n,{17}^n,{17}^{logn}$

Example $($with different functions$)$:

$1,3^{17}$

$logn,log2n$

$nsqrt(n)$

$n^5$

b$)$ For each function, explain why it has a larger rate of growth $($or the same rate of growth, if on the same line$)$ as the one before it$.$

HINTS:

review logs and exponents section of chapter $1$ in textbook, if needed

remember that $\sqrt[\phantom{2}]{n}$ is the same as $n^{0\mathrm{.}5}$

when in doubt about two functions $f(n)$ vs$.g(n),$ consider $logf(n)$ vs$.logg(n)$ or $2^{f(n)}$ vs$.2^{g(n)}$

a$)$ Algorithm X uses $10nlogn$ operations, and algorithm Y uses $n^2$ operations. Determine the value of $n_0$ such that $x$ is faster than $Y$ for $n{n}_0.$

b$)$ Repeat part $($a$)$ assuming that Y uses $n\sqrt[\phantom{2}]{n}$ operations

c$)$ Show that $2^{n+3}$ is $O(2^n)$ by finding the values of $n_0$ and $c$ such that $2^{n+3}c{2}^n$ for $n{n}_0.$ Explain why these values are correct.

NOTE: you may want to review logarithms and exponents first, in ch$.1$ of the textbook

d$)$ Show that $2^{3n}$ is not $O(2^n)$ by showing that such values of $n_0$ and $c$ do not exist. Alternately, you can do it by showing that for any positive constant $c,\underset{n}{lim}(\frac{2^{3n}}{2^n})>c$

Problem $2.$

a$)$ Order the following functions by the big$-O$ notation. If two functions are each is big$-O$ of the other, list them together.

$17nlogn,2^{17},loglogn,lo{g}^{17}n,2^{logn},sqrt(n),n^{0\mathrm{.}017},\frac{17}{n}$

$4n^{\frac{3}{2}},3n^{0\mathrm{.}5},17n,2nlo{g}^{2}n,2^n,nlo{g}_{17}n,{17}^n,{17}^{logn}$

Example $($with different functions$)$:

$1,3^{17}$

$logn,log2n$

$n\sqrt[\phantom{2}]{n}$

$n^5$

b$)$ For each function, explain why it has a larger rate of growth $($or the same rate of growth, if on the same line$)$ as the one before it$.$

HINTS:

review logs and exponents section of chapter $1$ in textbook, if needed

remember that sqrt$($n$)$ is the same as $n^{0\mathrm{.}5}$

when in doubt about two functions $f(n)$ vs$.g(n),$ consider $logf(n)$ vs$.logg(n)$ or vs$.2^{g(n)}$