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.


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