# Trying to find time complexity of modulus algorithm

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.

• What operation are you denoting with ^? That operator is commonly used for either exclusive-or or for exponentiation (power). Also, it seems incorrect that you are manipulating n in the first loop. Commented May 19, 2016 at 9:19
• Sorry. I've corrected it so that I'm manipulating e. I was copying it from my notebook where I was using n to represent the exponent. The ^ symbol was for exponentiation. By exclusive-or do you mean bitwise exclusive-or? Either way, I'll keep this in mind in the future. Commented May 19, 2016 at 9:55
• possible duplicate of What is O(…) and how do I calculate it?
– gnat
Commented May 19, 2016 at 10:28
• I know what big O is, but I can't figure out how to solve for it in this case. I'm simply wondering what the worst case time complexity for this algorithm is. Commented May 19, 2016 at 10:37
• I'm a little curious why, when you have arithmetic operators available, you're doing this instead of something like x - (trunc(x/n) * n). (Treating all of this as floats for simplicity.) Commented May 19, 2016 at 11:59