Consider the pseudocode below.

function $f(n)$

if $n2$

return $4**n$

$k=1$

for i from $1$ to $n$

for $j$ from $i$ to $n$

$k=2**k+12$

return $k+f(\frac{n}{2})+3**f(\frac{n}{3})$

Page $|5$

a$)(10$ pts$)$ Draw the first three levels $($including the root$)$ of a recursive tree for this function. Each

node should include T$(.).($Level $1(2$ pts$),$ Level $2(4$ pts$),$ Level $3(4$ pts$))$

b$)(15$ pts$)$ Write a recurrence relation describing the run time of this function.

Recurrence Relation Claim $(5$ pts$)$:

Show your work below on how you got this description $($hint: sum of atomic steps$)(10$ pts$)$:c$)(15$ pts$)$ Solve the relation and determine an asymptotic bound on the run time of this function

in big $O$ notation

Asymptotic Bound Claim $(5$ pts$)$: T$($n$)$ :

Show your work $($proof$)$ below $(10$ pts$)$: $($You can continue on the next page.$)$