Checking equality of integers: O(1) in C but O(log n) in Python 3?

Question

Consider these equivalent functions in C and Python 3. Most devs would immediately claim both are $O(1)$.

def is_equal(a: int, b: int) -> bool:
  return a == b

int is_equal(int a, int b) {
  return a == b;
}

But consider what is happening under the surface. Integers are just binary strings and, to determine equality, both languages will compare the strings bit-by-bit. In either case this scan is $O(b)$ where $b$ is the number of bits. Since integers have a constant size in bits in C, this is simply $O(1)$.

EDIT: C doesn't compare bit-by-bit see this answer

In Python 3 however, integers do not have fixed size and the scan remains $O(b)$ for the number of bits in the input, or $O(\log a)$ where $a$ is the value of the input in base 10.

So if you're analyzing code in Python, any time you compare two integers, you are embarking on a surprisingly complex journey of $O(\log n)$ with respect to the base 10 value of either number.

For me this raises several questions:

1. Is this correct? I haven't seen anyone else claim that Python compares ints in log time.
2. In the context of conducting an interview, should you notice or care if a candidate calls this $O(1)$?
3. Should you notice or care about this distinction in the real world?

EDIT: It is easily verified (and intuitive) that Python cannot compare arbitrarily large ints in constant time. So a better way to ask question 1 above might be "What (if any) is the justification for calling this operation $O(1)$? Because it's pragmatic? Conventional? Implied by the RAM model?

Answer 1

TL;DR: There is a CS convention of describing this type of operation as $O(1)$ which happens to break down in extreme cases for Python. These cases are extremely rare, so to break with the convention of $O(1)$ has negative utility. This kind of pragmatism is normal in big $O$.

There are a lot of very good responses to this question and I encourage you to read them. But I don't think any one of them fully answer my questions. So here's a synthesis.

Is this correct? I haven't seen anyone else claim that Python compares ints in log time.

This is surprisingly nuanced. It is true that Python compares very large ints in $O(\log n)$ runtime. But is it correct to describe this operation as $O(\log n)$?

Ultimately I'm most persuaded by this take from @TomvanderZanden:

If you said the C or Python version was $O(1)$ any interviewer should be perfectly happy. If you said it (the Python version) was $O(\log n)$ they would probably still be happy, but think you are a rather pedantic person who doesn't follow normal conventions.

and

If I was an interviewer, I would care whether you know the real-world limitations of what you are doing and know what theoretical concerns matter when and that you bring them up if and only if appropriate.

However I'm not accepting that as the answer because I think the first paragraph is currently misleading (happy to change).

Ultimately this argument is pragmatic. By the strict definition of big $O$ Python int comparison is still verifiably $O(\log n)$. But it is not useful to treat it that way, so you shouldn't. I would add that to be strict about big $O$ is to miss the point of big $O$ analysis.

Answer 2

Integers are just binary strings and, to determine equality, both languages will compare the strings bit-by-bit.

Not quite. C ints are machine-word-sized and compared with a single machine instruction; Python ints are represented in base $2^{30}$ (see e.g. https://rushter.com/blog/python-integer-implementation/) and compared digit-by-digit in that base. So the relevant base of the logarithm is $2^{30}$.

If at least one of numbers can be bounded by $2^{30d}$ for any fixed $d$, the comparison is $O(1)$ (because the number of digits is compared first), and if they can't, other operations are likely of much more concern than equality comparison. So in practice I'd say it's very unlikely to matter and if it does you'll know (and would be using not ints but something like the GNU Multiple Precision Arithmetic Library in C as well).

Answer 3

Complexity is defined relative to a computation model. P and NP, for example, are defined in terms of Turing machines.

For comparison, consider the word RAM model. In this model, memory is divided into words, words can be accessed in constant time, and the size of the problem can be represented using $O(1)$ words.

So, for example, when analysing a comparison-based sort operation, we assume that the number of elements $n$ can be stored in $O(1)$ words, so it takes constant time to read or write a number between $1$ and $n$.

Answer 4

Is this correct? I haven't seen anyone else claim that Python compares ints in log time.

No (and a little yes). Consider the following thought-provoking (but not really true) claim: A computer can only have a finite amount of memory (bounded by the number of atoms in the universe), so the Python version is also $O(1)$.

The problem is that we are trying to make a statement about asymptotics (pertaining to what happens at infinity) about a finite state machine (a computer). When we are analyzing the complexity of code, we don't actually analyze the code itself as it would run on a computer, we are analyzing some idealized model of the code.

Suppose I asked you to analyze a sorting algorithm written in C. You might state it uses ints to index the array, so it could only ever sort an array of size up to $2^{31}-1$. Yet, when we analyze such a piece of code, we pretend that it could handle arbitrarily large arrays. Clearly, we are not saying C integer comparison is $O(1)$ because it can only handle 32-bit numbers.

In the context of conducting an interview, should you notice or care if a candidate calls this O(1)?

Usually, not. Suppose I am conducting an interview and ask you to write a C or python computer program that counts the number of female employees appearing in the employee database.

It would be incredibly pedantic if I complained your C program was incorrect because it could only count up to $2^{31}-1$.

We generally assume that numbers are small enough that they can fit within one word/integer. We assume addition (or any other number operation) can be done in $O(1)$, because it would be very annoying to have to write $O(\log n)$ everywhere and it would just make everything unreadable even though $\log n$ is so small it doesn't really matter anyways.

If you said the C or Python version was $O(1)$ any interviewer should be perfectly happy. If you said it (the Python version) was $O(\log n)$ they would probably still be happy, but think you are a rather pedantic person who doesn't follow normal conventions.

Should you notice or care about this distinction in the real world?

Yes! It starts to matter when numbers get so large the assumption they are small is violated. Let's say you are interviewing for Google and they asked you to compute the number of search queries done by female users in the past year. The interviewer would be quite justified to complain if you wrote a C program using ints.

You could switch to using longs and still be justified in calling it $O(1)$, and similarly, calling the Python version $O(1)$ is also justified. The $O(1)$ v.s. $O(\log n)$ thing only starts to matter when the numbers get very long. For instance, if your task is to write a program that computes digits of $\pi$ or some similar task. If you wrote a Python program for this task and didn't mention the peculiarities of complexity when asked, the interviewer would care.

If I was an interviewer, I would care whether you know the real-world limitations of what you are doing and know what theoretical concerns matter when and that you bring them up if and only if appropriate.

When should you care?

So far, I've been a bit vague about "large" and "small" numbers. In the commonly used RAM model, you're allowed to assume that integer operations can be done in $O(1)$ on numbers that have at most $O(\log n)$ bits (where $n$ is the length of the input). The justification for this assumption is that if we have an input of length $n$, the pointers/indices in our programming language should be long enough to be able to address the entire input space. So, in the RAM model, if the input is binary number of $n$ (binary) digits, the complexity of checking equality is $O(\frac{n}{\log n})$ since we can check the equality of one group of $O(\log n)$ bits in one $O(1)$ operation.

Answer 5

Although this may seem like a trivial point, your first sentence is incorrect. The functions are not equivalent. To make them equivalent, the C function should use GMP (or similar) to implement arbitary-precision arithmetic. Now, the reason this observation is not trivial, is that the extent to which it's reasonable to say that the two are equivalent, is precisely the extent to which it's reasonable to say that the Python code is constant-time! That is, if we're going to ignore that Python's integers are bignums, we can (and should) consistently treat them as fixed size.

Analogously, consider the C function int is_equal(char a, char b) { return a == b; } and the Python function def is_equal(a: str, b: str) -> bool: return a == b. It is more obvious now that the functions are not equivalent, but the reason for that is exactly the same as the reason yours aren't. We just expect to see massive strings in Python all the time, but don't really expect massive ints even though of course we know they are possible. So, most of the time we ignore the fact that Python's integers are big, and we analyse as if they are fixed-size. In the rare cases where we care about the timings of bignum operations, you can use the "real" complexities. And, of course, also use GMP in your C code.

All this is to say: although you didn't realise it, you already know the answer to your restated version of your question at the end, and the answer is, "the same justification by which you described those functions as equivalent". Python is unusual in not having a fixed-size integer type (well, not one that people commonly use: it's possible to write one of course, and there's one in numpy). But as a matter of pragmatism, we don't want this to prevent us doing the "usual" complexity analysis of algorithms that crunch integers, and getting the "usual" answers. It is rarely necessary to provide the caveat that if we pass it a couple of 10GB integers that are nearly equal, it might take a little while to compare them.

In some cases you could formalise this (if you really need to) by saying that you're restricting your analysis to small integers. Then, you might consider complexity of some algorithm in terms of the size of some array of integers, treating all arithmetic operations as O(1). If you're considering algorithms which really are linear or worse in the magnitude of the integer, then you could formalise it by saying you're going to ignore the log-factor, since all you really care about is whether the complexity is closer to linear or quadratic, because O(n log n) is as good as linear for your purposes. Almost all the time, though, you don't need to formalise the complexity of algorithms in Python. If you've reached the point of specifying a programming language, you're not really doing abstract computer science any more ;-)

In the context of conducting an interview, should you notice or care if a candidate calls this $O(1)$?

Depends on interview for what, I suppose, but as a software professional, working primarily in Python for the last 10 years, I would not ask that in an interview. If I asked a question which had the complexity of integer comparison hidden inside it (like, I dunno, "what's the complexity of this sort algorithm?"), then I'd accept an answer which ignored the whole issue. I'd also accept one which addressed it. I do think it is worth understanding and computing complexity as part of practical programming, I just don't consider it that important for programming to be very careful about formally stating that you're talking about reasonable-sized integers.

I would also never ask a question in which I want the candidate to offer the information that Python integers are arbitrary-precision, when it's not obviously relevant to the the question for some reason to do with the data involved. If the question implies that the numbers involved can go higher than 2⁶⁴ then in a C interview I'd want the candidate to notice that this is a problem they need to deal with, and in a Python interview I'd want the candidate to know that it isn't, but I wouldn't expect them to go out of their way to state it. There isn't time in an interview to state every little fact that makes something a non-problem.

If I wanted to check understanding of complexity in an interview, then mostly likely I'd start by asking for some code for some problem where there's a really straightforward "naive" solution with poor complexity, and at least one less straightforward solution with decent complexity using well-known techniques. If the candidate offers the naive solution, then you can ask what the complexity is and how they'd modify the code to improve it. If the candidate offers a better solution then you can describe the naive solution, point out how few lines of code it is, and ask what's wrong with it (perhaps by asking, "if you were reviewing someone's code and they gave you this, what would you say about it"?). For most practical purposes all you care about is whether they can tell the difference between linear, quadratic, and worse-than-quadratic. O(n log n) also appears, but mainly because of sorting or data structures where you're talking about complexity in terms of the number of comparisons. The cost of each comparison is usually considered irrelevant, because the algorithm designer usually has no control over it (it's provided by the user of the algorithm or data structure).

In the astonishingly unlikely event that I was the interviewer for a position as a CS academic covering arbitrary-precision arithmetic, then certainly I would want candidates to know the complexities of various algorithms for various operations, and indeed to know the state of the art for the non-trivial ones.

Answer 6

Is this correct? I haven't seen anyone else claim that Python compares ints in log time. Python does indeed have an arbitrary precision integer format. However, we have to make a fair comparison here. If we consider the subset of integers on the bound of $[0,2^{64}]$, we find that the Python operation is constant time.

What you are seeing is one of the limits as to measuring computational complexity using big-oh notation. It describes what happens as n approaches infinity, but does not necessarily do a good job of comparing the behavior for smaller numbers. We see this famously in matrix multiplication algorithms. There are some algorithms which are more efficient in a big-oh sense, but are actually slower in practice until you get to gargantuan matrices.

In the context of conducting an interview, should you notice or care if a candidate calls this O(1)?

Depends on what you are hiring them for. For the vast majority of jobs, calling it O(1) should be fine. Indeed, it is how we tend to teach it in school. If you wanted to turn it into a useful opportunity to learn about your candidate, you might ask them why they think addition is constant time (to which the answer is that the model they used to determine big-oh assumed it... which is a valid answer)

If you are hiring someone to look for things like exploits in your code, you may want to push futher. A bignum produced by your own code is one thing, but is the user allowed to input the number of their own choosing? If so, they may be able to create timing attacks and DOSs using the fact that this addition can be terribly slow. Detecting this risk might be part of their job.

Should you notice or care about this distinction in the real world?

Practically speaking: no. Not until you acutally run into it, and fix the issue in debug. Python does a lot of things that are "generally safe" and are very efficient. This is why it has taken over as one of the most popular languages in the world.

For an equivalent situation: how fast is x.y in Python? We think of it as O(1), but there's actually a hash lookup there. That hash lookup uses a known probing mechanism, and the resulting lookup is actually O(n). You'll never see this in normal code. But in code where an adversary gets to fill your dictionary with their own content, they can intentionally craft keys that collide in this way.

Answer 7

I have never encountered a text that treated "regular" integer operations as anything besides constant time, with the implicit assumption that the size had some reasonable finite upper bound (for example 64 bits). Perhaps it would be more accurate to state the assumption, but to a CS audience, I think it is implicit.

Doing so would introduce a lot of complexity into discussions of essentially unrelated topics. Bigint implementations typically are not implemented bit by bit, but in base-(machine word size), so that O(b) > O(1) problem only kicks in for fabulously large numbers.

Personally while interviewing someone, I might appreciate the rigor and breadth of knowledge associated with knowing Python integers were arbitrary length, but anything beyond stating the assumption that all math is O(1) would feel extremely pedantic. If the analysis started getting too far off-topic with arithmetic, and wasted time, I would consider this a bad candidate.