Bellala's blog

What is the time complexity of calculating the inverse of n recursively？
By Bellala, history, 3 years ago, In English

I've always believed that getting the inverse of some integer n this way takes O(log(p)) time:

long long inv(long long n, long long p) {
	if (n == 1) return 1;
	return inv(p%n, p) * (p - p/n) % p;
}

But recently someone told me that it might be O(sqrt(p)).

So what is the correct time complexity?

  • Vote: I like it
  • +17
  • Vote: I do not like it

Comments Comments (5)
| Write comment?
»
3 years ago, # |
  Vote: I like it -13 Vote: I do not like it

It's the same as calculating gcd.

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +19 Vote: I do not like it

    I don't see, why does this hold. gcd swaps arguments, while in this function p is just parameter, it doesn't change during the recursion.

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      True, I'm not familiar with this code. I only know how to do this with the extended euclidean algorithm.

      → Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it

Apparently this algorithm is attributed to Gauss. You can make it guaranteed $$$O(\log n)$$$ by noticing that $$$p = nq + r = n(q+1) - (n-r)$$$ and $$$\min(r, n - r) \le \frac n2$$$.

But no one usually analyses your simpler one-liner version.

→ Reply
»
3 years ago, # |
  Vote: I like it +30 Vote: I do not like it

Its time complexity seems to be an open problem.

A common mistake is to consider it to be $$$O(\log(P))$$$ without thinking twice like above.

A problem discussed in this link is actually your problem.

And it gives an upper bound of $$$O(n^{1/3})$$$ and a lower bound of $$$\Omega(\dfrac{\log n}{\log\log n})$$$.

However it's not difficult to optimize it to $$$O(\log(n))$$$ as mmaxio shown above.

→ Reply