Give a C++ description of Algorithm Power for computing the power function p(x,n) (Code Fragment 4.4). Data

Question:

Give a C++ description of Algorithm Power for computing the power function p(x,n) (Code Fragment 4.4).


Data from in Fragment 4.4

Computing the power function using linear recursion.
To analyze the running time of the algorithm, we observe that each recursive call of function Power(x,n) divides the exponent, n, by two. Thus, there are O(logn) recursive calls, not O(n). That is, by using linear recursion and the squaring technique, we reduce the running time for the computation of the power function from O(n) to O(logn), which is a big improvement.

Fantastic news! We've Found the answer you've been seeking!

Step by Step Answer:

Related Book For  book-img-for-question

Data Structures And Algorithms In C++

ISBN: 9780470383278

2nd Edition

Authors: Michael T. Goodrich, Roberto Tamassia, David M. Mount

Question Posted: