0

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.

  • 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. – Bart van Ingen Schenau May 19 '16 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. – J O'fortune May 19 '16 at 9:55
  • possible duplicate of What is O(…) and how do I calculate it? – gnat May 19 '16 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. – J O'fortune May 19 '16 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 May 19 '16 at 11:59
0

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, privacy policy and cookie policy

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