$(100$ pts$)$ Let a constant k $>0$ be given. Suppose that for any n and x$,$ we are given functions pow$($n$,$ x$)$

which calculates n

x and log$($n$,$ x$)$ which calculates logn$($x$),$ both of which operate in $\backslash$Theta $($log n$)$ time.

$($i$)(75$ pts$)$ Calculate a tight $\backslash$Theta bound for the runtime of the following function f$,$ and argue that your

runtime is correct.

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

improvement is$.$

Note: this is a practice exercise and not intended to be a algorithm of practical utility.