Question

Consider the problem of computing x y for given integers x and y: we want the whole answer, not modulo a third integer. We know two algorithms for doing this: the iterative algorithm which performs y − 1 multiplications by x; and the recursive algorithm based on the binary expansion of y. Compare the time requirements of these two algorithms, assuming that the time to multiply an n-bit number by an m-bit number is O(mn).

Short answer

Time complexity of both the algorithms are compared.

Step-by-step solution

Explain Time Complexity

Time complexity is defined as the total amount of time taken to run and complete the function. It is being observed step by step at each statement of the function.Two integers x and y are considered and the exponential is found out by iterative and recursive approach and by comparing their time complexities.

Iterative algorithm

Iterative Algorithm is defined as:

$\begin{array}{l}\begin{array}{l}\mathrm{defiterative}(\mathrm{x},\mathrm{y}):\\ \mathrm{I}\mathrm{nput}=\mathrm{x},\mathrm{y}\end{array}\\ \mathrm{Output}={\mathrm{x}}^{\mathrm{y}}\\ \mathrm{Final}=\mathrm{x}\\ \mathrm{Foriinrange}(1,\mathrm{y}):\\ \mathrm{Final}\times =\mathrm{x}\\ \mathrm{ReturnFinal}\\ \end{array}$

Total time complexity of the given algorithm is $\mathrm{O}\left(2^{\mathrm{n}}\right)$.