Why is the time complexity of this divison algorithm O(LOG M)>

General Questions
#1

I don’t understand how does this run in O(log MOD), it is from the section modular inverses:

int inv(int x) {
    if (x <= 1) { return x; }
    return MOD - MOD / x * inv(MOD % x) % MOD;
}
1 Like
#2

Idk (maybe it does, but idk how to prove it).

Because it takes \mathcal{O}(\log p) time to compute a modular inverse modulo p,

I think this is referring to the method that uses exponentiation. Feel free to submit the contact form if you want the module to be clarified.

1 Like
#3

Note that a way to modify this code so that it definitely runs in O(\log \text{MOD}) time is to have x reduce to min(MOD % x, x - MOD % x). This way, x reduces by at least a factor of 2 every time.

1 Like
#4

I don’t think that, setting it to min(MOD % x, x-MOD%x) works.

1 Like