$1.$ Find a tight upper bound for f $($ n $)=$n $4+10$ n$2+5.$ Write your answer here: $\_\_\_\_\_\_\_(4$ points$)$

Prove your answer by giving values for the constants c and n $0.$ Choose the smallest integer value

possible for c$.(4$ points$)$

$2.$ Find an asymptotically tight bound for f $($ n $)=3$ n $32$n$.$ Write your answer here: $\_\_\_\_\_\_\_(4$ points$)$

Prove your answer by giving values for the constants c $1,$ c$2,$ and n $0.$ Choose the tightest integer

values possible for c $1$ and c$2.(6$ points$)$

$3.$ Is $3$ n$4\backslash$epsi $\backslash$Omega $($ n$2)?$ Circle your answer: yes $/$ no$.(2$ points$)$

If yes, prove your answer by giving values for the constants c and n$0.$ Choose the smallest integer

value possible for c$.$ If no$,$ derive a contradiction. $(4$ points$)$

$4.$ Write the following asymptotic efficiency classes in increasing order of magnitude.

O$($n$2),$ O$(2$n $),$ O $(1),$ O $($ n lgn $),$ O$($n$),$ O $($ n $!),$ O$($n$3),$ O $($ lg n $),$ O $($ n n $),$ O $($ n$2$ lgn $)(2$ points each$)$

$\_\_\_\_\_\_\_,\_\_\_\_\_\_\_\_,\_\_\_\_\_\_\_\_,\_\_\_\_\_\_\_\_,\_\_\_\_\_\_\_,\_\_\_\_\_\_\_,\_\_\_\_\_\_\_,\_\_\_\_\_\_\_,\_\_\_\_\_\_\_\_,\_\_\_\_\_\_\_$

$5.$ Determine the largest size n of a problem that can be solved in time t$,$ assuming that the algorithm

takes f$($n$)$ milliseconds. Write your answer for n as an integer. $(2$ points each$)$

a$.$ f$($n$)=$ n$,$ t $=1$ second $\_\_\_\_\_\_\_\_\_\_$

b$.$ f$($n$)=$ n lg n$,$ t $=1$ hour $\_\_\_\_\_\_\_\_\_\_$

c$.$ f$($n$)=$ n$2,$ t $=1$ hour $\_\_\_\_\_\_\_\_\_\_$

d$.$ f$($n$)=$ n $3,$ t $=1$ day $\_\_\_\_\_\_\_\_\_\_$

e$.$ f$($n$)=$ n $!,$ t $=1$ minute $\_\_\_\_\_\_\_\_\_\_$

$6.$ Suppose we are comparing two sorting algorithms and that for all inputs of size n the first algorithm

runs in $4$ n $3$ seconds, while the second algorithm runs in $64$ n lg $($n$)$ seconds. For which integer

values of n does the first algorithm beat the second algorithm? $\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_(4$ points$)$

CS $385,$ Homework $1$b: Analysis of Algorithms

Explain in detail how you got your answer or paste code that solves the problem $(2$ point$)$:

$\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_$

$\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_$

$7.$ Give the complexity of the following methods. Choose the most appropriate notation from among $\backslash$Omicron

$,\backslash$Theta $,$ and $\backslash$Omega $.(8$ points each$)$

int function$1($int n$)\{$

int count $=0$;

for $($int i $=$ n $/2$; i $<=$ n; i$++)\{$

for $($int j $=1$; j $<=$ n; j $*=2)\{$

count$++$;

$\}$

$\}$

return count;

$\}$

Answer: $\_\_\_\_\_\_\_\_\_$

int function$2($int n$)\{$

int count $=0$;

for $($int i $=1$; i $*$ i $*$ i $<=$ n; i$++)\{$

count$++$;

$\}$

return count;

$\}$

Answer: $\_\_\_\_\_\_\_\_\_$

int function$3($int n$)\{$

int count $=0$;

for $($int i $=1$; i $<=$ n; i$++)\{$

for $($int j $=1$; j $<=$ n; j$++)\{$

for $($int k $=1$; k $<=$ n; k$++)\{$

count$++$;

$\}$

$\}$

$\}$

return count;

$\}$

Answer: $\_\_\_\_\_\_\_\_\_$

int function$4($int n$)\{$

int count $=0$;

for $($int i $=1$; i $<=$ n; i$++)\{$

for $($int j $=1$; j $<=$ n; j$++)\{$

count$++$;

break;

$\}$

$\}$

return count;

$\}$

Answer: $\_\_\_\_\_\_\_\_\_$

CS $385,$ Homework $1$b: Analysis of Algorithms

int function$5($int n$)\{$

int count $=0$;

for $($int i $=1$; i $<=$ n; i$++)\{$

count$++$;

$\}$

for $($int j $=1$; j $<=$ n; j$++)\{$

count$++$;

$\}$

return count;

$\}$

Answer: