P$1.(10$ pts$)$ Proof by Induction $($Prove the two equations shown below$).$

o $(5$ pts$)$ Let Fi be the Fibonacci numbers as defined below.

F$0=1,$ F$1=1,$ and Fk$+1=$ Fk $+$ Fk$-1$

Prove

If you want to type your answer, this notation can above be written as 'Sigma i from $1$ to N$-2,$ F$\_$i $=$ F$\_$N $2\text{'}$

o $(5$ pts$)$ If n $>=7,$ then n$!>3^$n

The caret symbol $(^)$ can be used to raise a value to any power $($for example, N$2$ can be written as N$^2).$

P$2.(5$ pts$)$ Use the definition of Big$-$Oh to prove that following statement:

If f$($n$)$ is O$($g$($n$))$ and g$($n$)$ is O$($h$($n$)),$ then f$($n$)$ is O$($h$($n$))$

$($Hint: This statement can be proved easily by finding two constants given in the definition of Big$-$Oh$)$

P$3.(10$ pts$)$ For the following program fragments, give an analysis of the running time $($using $)$

i$)$

i $=1$

sum $=0$

while i $<$ n$*$n:

sum$+=1$

i $+=3$

i$)$

i $=1$

sum $=0$

while i $<$ n$*$n:

sum$+=1$

i $*=3$

ii$)$

k $=1$

n $=$ n $*$ k

if n $<10$:

k $=$ n

else:

for i in range$($n$)$:

for j in range$($n$)$:

iii$)$

for i in range$($n$)$:

for j in range$($i$*2,$ n$**3)$:

if j $>$ i:

for k in range$($n$**2)$:

sum$+=1$

iv$)$

for i in range$($n$)$:

for j in range$($i$*2,$ n$**3)$:

if j $<$ i:

for k in range$($n$**2)$:

sum$+=1$

P$4.(10$ pts$)$ What is the asymptotic complexity of the following functions? Justify your answer.

i$)$

def fun$1($n$)$:

sum $=0$;

if $($n $<1)$:

return $1$

else:

sum $=$ sum $+$ fun$1($n $-1)$

for i in range$($n$//2)$:

print$("*",$end$="")$

sum $+=$ i

return sum

Recurrence Relation:

Complexity in Big$-$Oh:

ii$)$

def fun$2($a$,$ b$)$:

if $($b $==0)$:

return $1$

if $($b $\%3==0)$:

return fun$2($a$*$a$,$ b$//3)$

elif:

return fun$2($a$,$ b$//3)*$a

Recurrence Relation:

Complexity in Big$-$Oh:

iii$)$ Assume $$combineAll$()$ is O$($n$)$ where n is $$right$-$left$.$

def fun$3($a$,$ left, right$)$:

if left $==$ right:

if a$[$left$]>0$:

return a$[$left$]$

else:

return $0$

center $=$ int$(($left $+$ right$)/2)$

caseLeft $=$ fun$3($a$,$ left, center$)$

caseRight $=$ fun$3($a$,$ center$+1,$ right$)$

caseLR $=$ fun$3($a$,($left$+$center$)//2,($center$+$right$)//2)$

combineAll$($caseLeft$,$ caseRight, caseLR$)$ # Assume it is O$($n$)$

Recurrence Relation:

Complexity in Big$-$Oh: