# 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. 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. May 19, 2016 at 9:55
• possible duplicate of What is O(…) and how do I calculate it?
– gnat
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. 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.) May 19, 2016 at 11:59

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`.