Is the following divide and conquer recursive algorithm for the exponentiation more efficient than the iterative one for large numbers? I have the two following algorithms. My analysis says that both of them are \$\mathcal O(m^24^n)\$ i.e they are equivalent for big numbers (more than 32 bits). Is this right? Note that m and n are the bits numbers for x and y
def pow1(x, y):
    if y == 0:
        return 1
    temp = x
    while y &gt; 1:
        y -= 1
        temp *= x
    return temp

def pow2(x, y):
    if y == 0:
        return 1
    temp = pow2(x, y//2)
    if y &amp; 1:    return temp * temp * x
    return temp * temp

The complexity of the first
y-1 iterations and in each iteration, a subtraction taking \$\mathcal O (\lg (y-i))\$, and a multiplication taking \$\mathcal O (im\cdot m)\$, hence the total work takes
\$T=\mathcal O(\sum\limits_{i=1}^ym^2i)=\mathcal O\left(m^2\frac{y(y+1)}2\right)=\mathcal O\left(m^24^n\right)\$
Of the second
We have \$n=\lg y\$ calls and for each, we have multiplications taking \$\mathcal O (2^im\cdot 2^im)\$, hence the total work takes
\$ T=\mathcal O\left(\sum\limits_{i=1}^{n}\left(4^im^2\right)\right)=\mathcal O\left({4^n}{m^2}\right)\tag{for large $n$}\$
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.