<< 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) becomes square(square(expmod base n m))
Since square(expmod base n m) takes a steps, feed it to square takes a + 1 steps
That'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 steps
We have to calculate them twice so they take 2a steps
That's O(n) growth