Please annswe these questions urgenttt!!$-$Short Answer: Analysis of Algorithms $[8$ points$]$

$1.$ Consider the following growth function: $[4$ points$]$

f $($n$)=12$n$2+42$log$($n$)+30$n$3$

$($a$)$ What is the Big$-$Oh order of this function? You should provide a relatively tight upper bound

$($e$.$g$.,$ not just $2$n$).[1$ point$]$

$($b$)$ Prove that your bound holds. $($Hint: the denition for Big$-$Oh is f $($n$)=$ O$($g$($n$))$ i $|$f $($n$)|<=$

c$|$g$($n$)|($for n $>$ x$0,$ where x$0$ is a constant, and c is also a constant$).[3$ points$]$

$2.$ What is the Big$-$Oh order of the following code fragment? The fragment is parameterized on the variable

n$.$ Assume that you are measuring the number of println calls. You should provide a relatively tight

upper bound. $[2$ points$]$

f o r $($ int i $=1$ ; i $<=$ n ; i $++)$

f o r $($ int j $=$ n $100$; j $>=0$ ; j $)$

f o r $($ int k $=1$ ; k $<=$ c ; k$++)$

System $.$ out $.$ p r i n t l n $("$ Nested l o o p s $!")$ ; $//$ c ou n t t h e s e

$3.$ Consider the following algorithm that implements matrix addition:

public Matrix p l u s $($ Matrix o t h e r $)\{$

i f $(!$ sameDimensions $($ o t h e r $))$ throw new RuntimeException $("$ I n c o m p a t i b l e $")$ ;

int $[][]$ r e s u l t $=$ new int $[$ data $.$ l e n g t h $][$ data $[0].$ l e n g t h $]$ ;

f o r $($ int y $=0$ ; y $<$ data $.$ l e n g t h ; y $++)$

f o r $($ int x $=0$ ; x $<$ data $.$ l e n g t h ; x$++)$

r e s u l t $[$ y $][$ x $]=$ data $[$ y $][$ x $]+$ o t h e r $.$ getElement $($ y $,$ x $)$ ;

return new S o l n M a t r i x $($ r e s u l t $)$ ;

$\}$

If you were choosing a cost metric $($i$.$e$.,$ what operation should be counted$),$ in order to determine this

algorithm's Big$-$Oh order, what operation would be the best choice? Explain. $[2$ points$]$

$4.$ If the induction proof for the towers of Hanoi problem used a base case of n$=5($instead of n$=1),$ would

it still be a valid proof? How would the truth that it aims assert be dierent than the n$=1$ proof? $[2$

points$]$