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)
//This first part above is clearly O(log x)
    while(e >= 1)
        while(n^e <= x)
            x -= n^e;
//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;

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.

  • 1
    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.)
    – Blrfl
    Commented May 19, 2016 at 11:59

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.