Question $2$: Recursion revisited.

Consider how to implement the "exponentiation" operation, i$.$e$.,$ given a real number $($double$)$

a and a positive integer $n,$ we want to find $a^n.$ Let us call this function pou$(\{$:$a,n)$

$($a$)[3]$ Consider the na$$ve implementation: pow$(a,n)=a*pow(a,n-1),$ with the base case

of $n=1,$ where we return $a.$ What is the running time of computing pou$(a,n?[$Justify

your answer with a line of reasoning.$]$

$($You may assume that multiplying two doubles takes $O(1)$ time.$)$

$($b$)[4]$ You ask ChatGPT if there's a smarter way, and it produces the following pseudocode:

Assuming that $n>1$ is a power of $2,$ write a recurrence for the running time of pon$(a,n$

$($note that it is a function only of $n).$ Obtain a closed form.