Give the asymptotic running time of each the following functions in

notation. That is, write down a recurrence relation for each recursive

function below and solve it. Show your work.

1 def Pow(x, n): 2 if n = 0: return 1 (a) end 5 return x * Pow(x, n-1 end