Let's generalize the fast exponentiation function that we wrote before:

The idea is to use the fact that

$x^n = (x^{n/2})^2$ if n is even

and

$x^n = x\times (x^{n//2})^2$ if n is odd.

(Check this by making sure that $x^7 = x\times (x^3)^2$.

def fast_exp(x, n):
    '''Return x^n
    '''
    
    if n == 0:
        return 1
    
    if n == 1:
        return x
        
        
    half_exp = fast_exp(x, n//2)
    if n % 2 == 0:
        return half_exp * half_exp
    else:
        return x * half_exp * half_exp

Let's consider the complexity. The call tree looks like this:

    1
    .
    .
   n/4
    |
   n/2
    |
    n

It's not the case here that every call takes the same amount of time: there is an extra multiplication for odd $n$. However, we can say that each call takes 2 multiplications or fewer. That means that each call takes at most k time for some constant k. So the total runtime is at most $k\log_2 n$, so the algorithm is $\mathcal{O}(\log n).