Exercise 1.26

When the square combination is evaluated, the expmod combination is evaluated once and then its value is substituted into the square compound procedure according to the substitution model. When the squaring is written as an explicit multiplication, the expmod combination is evaluated twice. The interpreter has no way of knowing that they will have the same value. This transforms a linear recursive process into a tree-recursive process. The time complexity of this tree-recursive process is \(\Theta(\log 2^n)\), or \(\Theta(n)\).