Time Complexity Of Integer Comparison In Python

What is the time complexity of integer comparison in Python for very large integers? For example, if we calculate factorial of 1000 using 2 functions, then check equality, is it O(

Solution 1:

There isn't a simple answer, but the answer is nevertheless obvious ;-)

That is, if two integers are in fact equal, it's impossible to know that without comparing all their bits. So in case of equality, the time needed is proportional to the number of bits (which is proportional to log(abs(N)) if N is one of the comparands).

If they're not in fact equal, there are several cases, all related to implementation internals. Long ints are stored as a vector of "digits" in a power-of-2 base. If the vectors don't have the same lengths, then the ints aren't equal, and that takes constant time.

But if they do have the same lengths, then the "digits" have to be compared until finding the first (if any) mismatching pair. That takes time proportional to the number of digits that need to be compared.

Then complicate all the above to account for possible mixtures of signs.