Editing Exponentiation by squaring (section)

==Computational complexity==

A brief analysis shows that such an algorithm uses <math>\lfloor \log_2n\rfloor</math> squarings and at most <math>\lfloor \log_2n\rfloor</math> multiplications, where <math>\lfloor\;\rfloor</math> denotes the [[floor function]]. More precisely, the number of multiplications is one less than the number of ones present in the [[binary expansion]] of ''n''. For ''n'' greater than about 4 this is computationally more efficient than naively multiplying the base with itself repeatedly.

Each squaring results in approximately double the number of digits of the previous, and so, if multiplication of two ''d''-digit numbers is implemented in O(''d''<sup>''k''</sup>) operations for some fixed ''k'', then the complexity of computing ''x''<sup>''n''</sup> is given by

: <math>
 \sum\limits_{i=0}^{O(\log n)} \big(2^i O(\log x)\big)^k = O\big((n \log x)^k\big).
</math>