# sicp-ex-1.26

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.

tiendo1011

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