¡Elevar a una potencia es más rápido que n multiplicaciones! Para ello, utilice las siguientes relaciones de recurrencia:
\(a^n=(a^2)^{n/2},\ for \ even \n, \\ a^n=a \cdot a^{n-1 },\ por \impar\n.\)
Implemente el algoritmo de exponenciación rápida. Si hace todo bien, la complejidad de su algoritmo será O(logn) .