$($Given a picture of Algorithm $2$ from lecture notes above answer the following questions...$)$

$1.$ Modify the algorithm to cube b instead of squaring it in every re$-$

cursive call. $[0\mathrm{.}5$ point$]$

$2.$ Given inputs b and p in Z$+,$ what are the best$-$case, worst$-$case, and average$-$case complexity of the modified algorithm? $[0\mathrm{.}5$ point$]$

$3.$ Identify the inputs for which your algorithm performs the minimum

and those for which the algorithm performs the maximum number

of computations in terms of your inputs $($not exact numbers, but the

properties that have to be satisfied by the said inputs$).[0\mathrm{.}5$ point$]$

$4.$ Use big$-$O$,$ big$-\backslash$theta $,$ and big $$ notation to measure the performance of your algorithm. Justify your answers. $[0\mathrm{.}5$ point$]$

$5.$ How does your algorithm perform compared to Algorithm $2$ in the

notes. $[0\mathrm{.}5$ point$]$