Note: There are bonus points listed for some questions, but you do not need to complete all other questions before attempting the bonus questions.

Problem $1(40$ pts$).$

$($a$)(10$ pts$)$ Prove that f $=$ O$($g$)$ if and only if g $=52($f$).$ Note that you have to prove both directions.

$($b$)(10$ pts$)$ Using induction, prove that n$!=$ O$($n$").$

$($c$)(20$ pts$)$ Let a constant k $0$ be given. Suppose that for any n and x$,$ we are given functions pown, x$)$ which calculates n$*($e$.$g$.$ with divide$-$and$-$conquer$),$ and log$($n$,$ x$)$ which calculates log$,($x$),$ both of which operate in O$($log

n$)$ time.

$($i$)(15$ pts$)$ Calculate a tight $$ bound for the runtime of the following function f$,$ and argue that your runtime is correct.

$($ii$)(5$ pts$)$ Briefly describe a simple way we can improve the runtime of this algorithm, and what the

improvement is$.$

$1$: function f$($n$)$

i $=1$

x $=0$

while i $<$ n do

in

i $*=$ pow$($n$,1/$k$)$

j$=0$

$7$:

$8$:

whilej $<$ log$($n$,$ i$)$ do x$+=$j

j$+=1$

$10$: returnx