Exercise $11$

Exercise $16$

Exercises $19,20,21$

Exercise $25$

Exercise $32$

algorithm.

$4.$ Write an Insertion Sort algorithm $($Insertion Sort is discussed in Section $7\mathrm{.}2)$ that uses Binary Search to find the position where the next insertion sould take place.

$11$

Determine the worst$-$case, average$-$case, and best$-$case time complexities for the basic Insertion Sort and for the version given in Exercise $4,$ which uses Binary Search

$16$

Using the definitions of $O$ and $,$ show that

$6n^2+20$ninO$(n^3),$ but $,6n^2+20n!in(n^3).$

$19$

The function $f(x)=3n^2+10nlogn+1000n+4logn+9999$ belongs in which of the following complexity categories:

$($a$)(lgn)$

$($b$)(n^{2}logn)$

$($c$)(n)$

$($d$)(nlgn)$

$($e$)(n^2)$

$($f$)$ None of these

$20$

The function $f(x)=(logn{)}^2+2n+4n+logn+50$ belongs in which of the following complexity categories:

$($a$)(lgn)$

$($b$)((logn{)}^2)$

$($c$)(n)$

$($d$)(nlgn)$

$($e$)(n(lgn{)}^2)$

$($f$)$ None of these

$21$

The function $f(x)=n+n^2+2^n+n^4$ belongs in which of the following complexity categories:

$($a$)(n)$

$($b$)(n^2)$

$($c$)(n^3)$

$($d$)(nlgn)$

$($e$)(n^4)$

$($f$)$ None of these

Suppose you have a computer that requires $1$ minute to solve problem instances of size $n=1,000.$ Suppose you buy a new computer that runs $1,000$ times faster than the old one. What instance sizes can be run in $1$ minute, assuming the following time complexities $T(n)$ for our algorithm?

$($a$)T(n)=n$

$($b$)T(n)=n^3$

$($c$)T(n)={10}^n$

What is the time complexity $T(n)$ of the nested loops below? For simplicity, you may assume that $n$ is a power of $2.$ That is$,n=2^k$ for some positive integer $k.$

for

$j=n$;

while

$$ body of the while loop$>//$Needs $(1).$

$\}$

$j={|}_{{?}_{?}}\frac{j}{2_{{?}_{?}}}|$;

$\}$