Trying to find time complexity of modulus algorithm

Question

I can't quite figure out the time complexity of this algorithm I've written for finding the modulo. I've added it here 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

Hopefully I'm not missing anything obvious, but this doesn't seem like an easy problem to solve. Thanks in advance. EDIT: By the way, ^ represents exponentiation in this case, just to avoid confusion.

Answer 1

Complexity is O(log(x) * n), or O(log(x) * (n - 1)) if you want the exact upper bound.

Why? Because the inner loop can be determined to have at most n - 1 iterations each.

You can provoke the worst case for x = n^i - 1 for any positive integers x, n and i.