8
$\begingroup$

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?

Improve this question
$\endgroup$
10
  • 5
    $\begingroup$ "I haven't seen anyone else claim that Python compares ints in log time" -- here is an example of Tim Peters (inventor of Python's TimSort, among many other contributions to Python), saying exactly that: stackoverflow.com/a/44061819/13005. This being the CS site, possibly we should say it's linear, anyway, since we should conventionally be analysing complexity in terms of the size in bits of the input, not the magnitude of the value the input represents :-) $\endgroup$ – Steve Jessop Jul 4 '20 at 1:34
  • 2
    $\begingroup$ In every interview setting I experienced, the input was bounded and calling this O(1) is correct. Also, I would take more issue with someone who couldn't explain the behavioural difference between the two program (arbitrary precision vs 64 bit) than someone assuming O(1) for the python one, since the latter is in almost all contexts legitimate under business constraints - even for crypto code, although the constants involved can be quite large, they are still bounded. Not posting this as an answer, since it doesn't quite fit the theoretical nature of CS-exchange. $\endgroup$ – WorldSEnder Jul 4 '20 at 2:42
  • $\begingroup$ The fact that it is more expensive to work with big ints is one of the reasons that numpy can provide a speed boost over base Python. The problem has also been discussed as part of the Python 2 to Python 3 transition. See Why is Python 2.7 faster than 3.2? $\endgroup$ – John Coleman Jul 4 '20 at 14:53
  • 1
    $\begingroup$ This appears to be an issue of when to define computational complexity in terms of the number of inputs vs the bit-complexity (or log of the magnitude) of the input. Does this article help? en.m.wikipedia.org/wiki/Context_of_computational_complexity $\endgroup$ – RBarryYoung Jul 4 '20 at 17:21
  • $\begingroup$ You mention base 10 twice. Why do you think base 10 comes into play? You still talk about bits, so I'm very confused about what you think. $\endgroup$ – JiK Jul 4 '20 at 19:33
25
$\begingroup$

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).

Improve this answer
$\endgroup$
4
  • 17
    $\begingroup$ If you compare the same numbers as the C program does, then you know the numbers are < 2^64, so d <= 3. In practice, most numbers that are compared are less than 2^30 so d = 1. But if you need to compare integers around 10^10000, then C doesn't do that out of the box, and you need to write C code running in O (log n). $\endgroup$ – gnasher729 Jul 3 '20 at 8:29
  • 1
    $\begingroup$ Yes, I was thinking about saying this explicitly and don't remember why I didn't. $\endgroup$ – Alexey Romanov Jul 3 '20 at 9:14
  • 1
    $\begingroup$ Special case for the first paragraph: 8-bit machines like AVR (8-bit RISC microcontroller) need 2 registers to hold an int (C requires int to be at least 16 bits). This means compare is a fixed sequence of sub / sub-with-carry. (Actually cp/cpc which is like sub but doesn't store the integer result, only flags). godbolt.org/z/pAy8sc. That doesn't spoil your point, and your phrasing is a useful simplification of the thorny details of C portability. $\endgroup$ – Peter Cordes Jul 4 '20 at 0:41
  • 1
    $\begingroup$ C doesn't say anything about how many machine instructions are used to compare ints. $\endgroup$ – Remember Monica Jul 4 '20 at 4:45
16
$\begingroup$

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$.

Improve this answer
$\endgroup$
11
  • 8
    $\begingroup$ @jtschoonhoven The RAM model is far more common. $\endgroup$ – Tom van der Zanden Jul 3 '20 at 9:31
  • 1
    $\begingroup$ @jtschoonhoven : Yes. An arbitrary length string of characters is not assumed to fit in a (prespecified constant number of) word(s) while an integer type (necessarily fixed width) is assumed to fit in a constant number of words. $\endgroup$ – Eric Towers Jul 3 '20 at 18:41
  • 1
    $\begingroup$ @jtschoonhoven : Python integers are not always represented as variable length arrays of words. And, in "almost all" programming languages (and models of typed computation) integral types are fixed width. Python is bizarre in having an integral type that silently switches representation between global constant objects ($O(1)$ compare), a fixed-width integral type (in the usual sense of the word) ($O(1)$ compare), and a variable length array of words ($O(\log n)$ compare). Why would you expect general language to apply to a bizarre example? $\endgroup$ – Eric Towers Jul 3 '20 at 19:35
  • 4
    $\begingroup$ @jtschoonhoven : You cannot describe its behaviour accurately. Its behaviour is strongly dependent on the implementation. The $O(1)$ shortcut to compare signs or zero via struct member ob_size is not standardized among implementations. The range $[-5,256]$ of global constant objects is not standardized and an implementation may use a larger range. The representation as a hardware compatible (possibly multiprecision) integral type is guaranteed for the interval $[-2^{30},2^{30}]$ but an implementation is permitted to use a larger range. Implementations are free to find more shortcuts. $\endgroup$ – Eric Towers Jul 3 '20 at 19:54
  • 1
    $\begingroup$ @EricTowers In big $O$ we're concerned with bounding the worst case, so shortcuts are not typically relevant unless they apply in all cases. As $n$ approaches infinity, in all common implementations the behavior will be $O(\log n)$. If we knew the range of possible inputs then it would be $O(1)$ by definition, but that's not what I'm asking. $\endgroup$ – jtschoonhoven Jul 4 '20 at 5:41
9
$\begingroup$

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.

Improve this answer
$\endgroup$
8
  • 4
    $\begingroup$ "A computer can only have a finite amount of memory (bounded by the number of atoms in the universe), so the phyton version is also O(1)." - By that reasoning, you can reduce any algorithm to O(1) complexity. The number of nodes in a graph is bounded in a similar way, so TSP? O(1). It's an utterly useless argument. If you want to argue that in this case O(log n) doesn't really come into play in practical scenarios, then argue that. I'd agree. But don't pretend O(log n) = O(1) because the number of atoms in the universe is bounded. $\endgroup$ – marcelm Jul 3 '20 at 17:17
  • $\begingroup$ @marcelm I am not saying (which I should perhaps have made clearer, I can see it comes across badly now) we should treat everything as $O(1)$ or that it is sensible to say that Python addition is $O(1)$. It is meant as a though-provoking introduction to the answer to get the reader thinking about applying asymptotic analysis to real-world computers. No real-world implementation of C nor Python can handle arbitrarily large numbers. $\endgroup$ – Tom van der Zanden Jul 3 '20 at 18:54
  • 1
    $\begingroup$ I like this answer a lot but after the first edit I still don't feel convinced by the opening thought experiment and I'm hesitant to accept it as the answer. Comparing two strings is commonly described as $O(n)$ for the length of the shorter string: if Python integers behave similarly, why would it be different? Other than that it would be pedantic (which is true). I think what you're getting at is that it is correct to describe this operation as $O(\log n)$ but almost never useful. $\endgroup$ – jtschoonhoven Jul 3 '20 at 20:25
  • $\begingroup$ @jtschoonhoven: Perhaps you're thinking of implicit-length strings where finding the length also costs O(n) work, which you can do while comparing (like C strcmp that works on 0-terminated C strings). Explict-length strings like C++ std::string can early-out by comparing the lengths in O(1) time because the length is stored in a known place. To avoid overread of the shorter array, you have to compare the lengths anyway; if you know the lengths are different it makes no sense to actually scan the arrays for equality, unless you're actually checking that A is a prefix of or equal to B. $\endgroup$ – Peter Cordes Jul 4 '20 at 0:51
  • 2
    $\begingroup$ @jtschoonhoven: But in the common case of normal problems, e.g. using huge amounts of small integers as problem size scales up, each individual integer still only costs O(1) to operate on. If scaling up n for the problem you were talking about did involve larger and larger integers, then yes you'd need to account for that whether you wrote it in Python and let the interpreter do it, or whether you wrote it in C and the BigInt stuff was a more visible part of the source code. $\endgroup$ – Peter Cordes Jul 4 '20 at 6:12
6
$\begingroup$

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 264 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.

Improve this answer
$\endgroup$
6
  • $\begingroup$ Right, that the functions are not actually equivalent is the point. This question is somewhat contentions because there is a convention of considering integer comparisons as $O(1)$ which breaks down in extreme cases that are specific to Python. My question is ultimately about whether this matters in practice, and I agree with your assessment that (usually) it doesn't. $\endgroup$ – jtschoonhoven Jul 4 '20 at 5:20
  • $\begingroup$ @jtschoonhoven: and in particular that the way they're inequivalent is that the Python one is "more powerful", but almost all the time we aren't using that power (and if pressed we could formally prove we aren't). Therefore it's mildly misleading to make too much of the fact that in some sense we "should" have to pay for that power in complexity. We're not really paying for the power of the Python function, we're at most paying for our laziness in not properly formalising some practical restrictions on the domain of the function. $\endgroup$ – Steve Jessop Jul 4 '20 at 15:19
  • $\begingroup$ You're missing a ; in your C function, like the question. $\endgroup$ – Peter Cordes Jul 4 '20 at 22:52
  • $\begingroup$ @jtschoonhoven: in fact it's just occurred to me that int in Python can be subclassed. Therefore, even if the type hints are enforced (which typically in Python they aren't), the Python function is even less equivalent to the C function than I've already outlined. == does not necessarily call the int equality operation. It is a call to arbitrary user code, and we have no way to analyse what its time complexity might be. So there's another way to formalise, which is to refuse to speak in those terms and merely say the complexity of the code is O(1) comparisons. $\endgroup$ – Steve Jessop Jul 5 '20 at 14:37
  • $\begingroup$ ... once we have some information about what gets passed into the function, maybe then we can talk time complexity in terms of cycle count or what-have-you :-) $\endgroup$ – Steve Jessop Jul 5 '20 at 14:39
1
$\begingroup$

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.

Improve this answer
$\endgroup$
10
  • $\begingroup$ My understanding is that big O supposedly always refers to worst-case performance unless otherwise specified. But I hear hash table lookups frequently referred to as O(1) without specifying we mean average performance. This is probably pragmatic, but the inconsistency in the industry has made this confusing for me. $\endgroup$ – jtschoonhoven Jul 3 '20 at 16:40
  • 2
    $\begingroup$ @jtschoonhoven Big-Oh is "worst-case," but practically speaking it only speaks of the worst case as "n" approaches infinity. It's an artifact of how there's a constant-multiple hidden in the definition. For any finite "n", every algorithm is O(1), as you can always select a constant large enough. And yes, the mislabeling of hash tables as O(1) stems from the fact that O(n) scares people, but practically speaking hash tables have amazing performance. I will tell people "you can treat it like O(1), as long as you don't have an intelligent adversary choosing your keys" $\endgroup$ – Cort Ammon Jul 3 '20 at 17:17
  • 3
    $\begingroup$ @jtschoonhoven big-O isn't "best-case", "worst-case", or "average-case". It's "bounded above by", contrast with big-omega, which is "bounded below by" and big-theta, which is "bounded above and below by" $\endgroup$ – Caleth Jul 3 '20 at 18:01
  • 1
    $\begingroup$ @jtschoonhoven The answer is really "it depends." Technically, the operation is indeed O(log n). However, what it is showing here is that Big-oh is not really telling you the story you need to really understand what is going on. Its the wrong tool for the job in 99% of these integer cases, only being the important way to think about things in a handful of unbounded cases (such as doing RSA cryptography). Big-oh is really overrated in a lot of these situations. $\endgroup$ – Cort Ammon Jul 3 '20 at 19:38
  • 2
    $\begingroup$ And there isn't technically anything "wrong" about saying its O(1), as long as your model is measuring the number of additions. Just like how in C++, we don't consider the feed-forward nature of addition in the hardware which actually takes O(log n) time, but we never treat it as such (beacuse even if we finish quickly, we still wait for the end of a cycle before propagating the bits to the next stage of the pipeline) $\endgroup$ – Cort Ammon Jul 3 '20 at 19:42
0
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Agree and my question isn't meant to be pedantic. I'm still getting a sense of how strict one is expected to be with big $O$ and when you're allowed to make reasonable, implicit assumptions like this. $\endgroup$ – jtschoonhoven Jul 3 '20 at 23:41
  • 1
    $\begingroup$ @jtschoonhoven Asking here is definitely not pedantic! Thinking about how numbers are stored is also generally a good idea, even if not in big-O. I think the CLRS Algorithms book actually specifically addresses assumptions, but I can't seem to find my copy. I will dig around for it and see if I can find a reference for you. $\endgroup$ – trognanders Jul 4 '20 at 1:54
0
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Are there other examples like this where we ignore some nuance and call a technically-more-complex operation O(1)? I assume there must be many. Inserting to a hash table doesn't count because we still teach that this is O(n) worst case. $\endgroup$ – jtschoonhoven Jul 5 '20 at 20:17
  • $\begingroup$ One example of this: looking up a string of length k in a hash table is technically O(k) even in the best case, because every char of k must be read. But strings are generally assumed to be "reasonably small" enough that this is commonly ignored. $\endgroup$ – jtschoonhoven Jul 8 '20 at 23:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.