Is the following divide and conquer recursive algorithm for the exponentiation more efficient than the iterative one for large numbers?
I think your analysis is correct if multiplication of k-digit and ℓ-digit numbers takes Θ(kℓ) time, but more efficient multiplication algorithms are known. The most efficient algorithm in wide use (implemented in GMP) is Schönhage-Strassen, which is O(k log k log log k) for numbers of equal length. I don't know the complexity for unequal lengths, but I suspect it's O(ℓ log k log log k) for k &lt; ℓ. Using that algorithm, or any sub-kℓ algorithm, you should find that the divide-and-conquer approach is faster.