CPS $3440$: Unit $1$ Assignment

Suppose we are comparing implementations of insertion sort and merge sort

on the same machine. For inputs of size $n,$ insertion sort runs in $4n^2$ steps,

while merge sort runs in $32nlgn$ steps. For which values of $n$ does insertion

sort beat merge sort?

Rewrite the INSERTION$-$SORT procedure to sort into nonincreasing instead

of nondecreasing order.

Express the function $\frac{n^5}{1000}-100n^2-100n+3$ in terms of $-$notation.

Show that for any real constants a and $b,$ where $b>0,(n+a{)}^b=(n^b).$

Yes or No $-$ is $2^{n+1}=O(2^n)?$ Why?

Yes or No $-$ is $2^{2n}=O(2^n)?$ Why?