Consider the exponentiation algorithm described. Let T(n) denote the running time to compute Xn. Write down the recurrences for the running time of the algorithm and base case.

1 long 1ong pow long-long x, int n ) 2 if( n == 0 ) if(n1) 7 if isEven ( n)) return 1; return x; return pow( x *x, n /2 ); else 0 return pow( x * x, n / 2) *x