def power(xn) """compute the value for integer "" if = return else partial power(xn / rely on truncated division result partial partial if = if oddinclude extra factor of result return result code fragment computing the power function using repeated squaring to illustrate the execution of our improved algorithmfigure provides recursion trace of the computation power( return power( return power( return = power( return = power( return power( figure recursion trace for an execution of power( to analyze the running time of the revised algorithmwe observe that the exponent in each recursive call of function power( ,nis at most half of the preceding exponent as we saw with the analysis of binary searchthe number of times that we can divide in half before getting to one or less is (log nthereforeour new formulation of the power function results in (log nrecursive calls each individual activation of the function uses ( operations (excluding the recursive calls)and so the total number of operations for computing power( ,nis (log nthis is significant improvement over the original ( )-time algorithm the improved version also provides significant saving in reducing the memory usage the first version has recursive depth of ( )and therefore (nactivation records are simultaneous stored in memory because the recursive depth of the improved version is (log )its memory usages is (log nas well