Блог пользователя Bellala

What is the time complexity of calculating the inverse of n recursively？
Автор Bellala, история, 4 года назад, По-английски

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?

  • Проголосовать: нравится
  • +17
  • Проголосовать: не нравится

»
4 года назад, скрыть # |
 
Проголосовать: нравится -13 Проголосовать: не нравится

It's the same as calculating gcd.

→ Ответить
»
4 года назад, скрыть # |
← Rev. 2  
Проголосовать: нравится +3 Проголосовать: не нравится

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.

→ Ответить
»
4 года назад, скрыть # |
 
Проголосовать: нравится +30 Проголосовать: не нравится

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.

→ Ответить