With the following lines of code below, give the asymptotic running time of each of the following functions in ? notation. That is, write down a recurrence relation for each recursive function below and solve it. Show your work.

Transcribed Image Text:

(b) (c) 1 def Pow(x, n): if n == 0: | return 1 2 end 3 5 6 7 8 9 5 6 7 10 11 end 8 # n is even if n % 2 == 0: return Pow(x, n/2)* Pow(x, n/2) 1 def Pow(x, n): 2 if n == 0: 3 9 end 10 11 #n is odd return x Pow(x, n/2) * Pow(x, n/2) return 1 end f= Pow(x, [n/2]) #n is even if n %2 == 0: return f* f end 12 13 end # n is odd return r * f* f (b) (c) 1 def Pow(x, n): if n == 0: | return 1 2 end 3 5 6 7 8 9 5 6 7 10 11 end 8 # n is even if n % 2 == 0: return Pow(x, n/2)* Pow(x, n/2) 1 def Pow(x, n): 2 if n == 0: 3 9 end 10 11 #n is odd return x Pow(x, n/2) * Pow(x, n/2) return 1 end f= Pow(x, [n/2]) #n is even if n %2 == 0: return f* f end 12 13 end # n is odd return r * f* f