CODEWITHSUNDEEP
javaperformancecomplexity-theory
Mhsz
Mhsz

Reputation: 233

time complexity for most programming language?

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.

Upvotes: 2

Views: 254

Answers (1)

nwellnhof
nwellnhof

Reputation: 33618

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.

Upvotes: 1

Related Questions