<< Previous exercise (1.25) | sicp-solutions | Next exercise (1.27) >>

Instead of a linear recursion, the rewritten `expmod` generates a tree recursion, whose execution time grows exponentially with the depth of the tree, which is the logarithm of *N*.
Therefore, the execution time is linear with *N*.

To simplify, we'll find the different between

square(expmod base n m)and* (expmod base n m) (expmod base n m)1.

square(expmod base n m)(Let's assume it takes a steps)Double the size of the input:

square(expmod base 2n m)becomessquare(square(expmod base n m))Since

square(expmod base n m)takes a steps, feed it to square takes a + 1 stepsThat's O(log n) growth

2.

* (expmod base n m) (expmod base n m)(Lets assume they take a steps)Double the size of the input:

* (expmod base 2n m) (expmod base 2n m)becomes

* (* (expmod base n m) (expmod base n m)) (* (expmod base n m) (expmod base n m))Each

* (expmod base n m) (expmod base n m)takes a stepsWe have to calculate them twice so they take 2a steps

That's O(n) growth