Cercando di trovare la complessità temporale dell'algoritmo del modulo

Non riesco a capire la complessità temporale di questo algoritmo che ho scritto per la ricerca del modulo. L'ho aggiunto qui in psuedocode.

Modulo(int x, int n)
// x is the dividend, n is the divisor
    e := 1;
    while(n^e < x)
        e++;
    end
    e--;
//This first part above is clearly O(log x)
    while(e >= 1)
        while(n^e <= x)
            x -= n^e;
        end
        e--;
    end
//This second part above is more challenging. The outer loop goes through log x cycles, while the inner loop goes through (x mod (n^(e+1)))/(n^e) cycles.
    return x;
end

Spero che non mi sfugga nulla di ovvio, ma questo non sembra un problema facile da risolvere. Grazie in anticipo. EDIT: A proposito, ^ rappresenta l'esponenziazione in questo caso, solo per evitare confusione.