Chapter 1, Building Abstractions with Procedures

Section - Procedures and the Processes They Generate

Exercise 1.26

The change made in function expmod by Louis Reasoner will cause expmode to be called twice in each recursive invocation.

The process becomes tree recursive as each invocation results in two branches. Clearly the height of the tree is $log_2 \, (base)$ where $base$ is the input to this procedure.

Also note that number of steps in the process is equal to total number of nodes in the tree.

Thus total nodes in the tree are $2 \cdot 2 \cdot 2 \cdot \cdot \cdot (log_2 \, (base) \text{ times }) = 2^{ log_2 \, (base) } = base$.

Thus number of steps is equal to the input passed i.e. $\theta (n)$. As we can see this small mistake converted this code from $log_2 \, n$ complexity to $n$ order complexity.