time complexity for most programming language?

Question

I read about time complexity modular arithmetic in many books . there is thing I don't understood . I read in some books the following

For any a mod N, a has a multiplicative inverse modulo N if and only if it is relatively prime to N. When this inverse exists, it can be found in time O(n^3) (where as usual n denotes the number of bits of N) by running the extended Euclid algorithm. My question revolves around *extended Euclid algorithm* *is has O(n^3)*

when I write in java integrated with netbeans or C# or C++ program this line

A = B.modInverse(N) //here by java syntax

In general. Can I say usually this line has time complexity O(n^3).

or necessary write the same steps extended Euclid algorithm.

I think this is offtopic, it belongs to one of the computer science sites. — sharp12345
– sharp12345, Commented Feb 15, 2013 at 22:44
No. The question, once you unpick it, is about the implementation of modInverse() in Java and C#. — user207421
– user207421, Commented Feb 15, 2013 at 22:55

nwellnhof · Accepted Answer · 2013-02-25 12:42:04Z

1

Unless the documentation of the modInverse method makes an explicit guarantee about its time complexity, you generally can't make any assumptions about its running time. The implementation could be completely different depending on the runtime/library or even the version of the runtime.

If you have access to the source code, you can verify which algorithm is used. You can also run your own benchmarks for different input sizes and you'll get a pretty good picture about the asymptotic behavior of the concrete implementation.

That said, it's highly probable that popular libraries for arbitrary-precision arithmetic use the best known algorithms for basic operations like modInverse.

answered Feb 25, 2013 at 12:42

nwellnhof

34.1k7 gold badges97 silver badges121 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

time complexity for most programming language?

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related