Solution to Exercise 1.26:
Because Louis’s version makes two calls to expmod for the even case instead of one, his process comes to resemble a binary tree of depth log n. The original creates a process that resembled a chain of length log n. When we count the number of nodes in Louis’s binary tree we get n – 1, bringing it back to Θ(n).
Ken Dyck 