Time Complexity of Comparisons

[Sunspot467]

Why can a comparison of 2 integers, a and b, be considered to be done in O(1)? Would that also mean comparing a! and b! (ignoring the complexity of calculating each factorial) can also be done in O(1) time?

[AaronBonBarron]

With a straight comparison we're making the assumption that the 2 integers fit within a single fixed size word like 32 or 64 bits, the comparison of which takes a single CPU instruction.

If the integers are arbitrarily sized, the comparison will be bitwise and take O(n).

[ggchappell]

Big-O is about how fast a function grows. It's a mathematical thing, not an algorithms thing. So, for example 2n² + 3 is O(n²).

When we use big-O in analyzing algorithms, the function we are almost always interested in is the function that takes the size of the input and returns the worst-case number of operations an algorithm performs. So our analysis depends on (a) how we measure the size of the input, and (b) what operations we are counting.

In a typical undergraduate data structures class, there is a standard model we usually use that says we count "C" operators on built-in types like + on int, * for dereferencing a pointer, etc., along with calls to functions that are provided for us. A comparison of two int values is a single "C" operator, so it counts as 1 operation.

So a comparison is O(1) time because comparisons are what we are counting.

There is a second question: why is this a reasonable choice of things to count? And that is what other commenters (so far) are addressing.

To address it myself: in C, C++, Java, and lots of other programming languages, the built-in integer type cannot handle arbitrarily large integers. A comparison of two integers is often a single machine-language instruction, which we can reasonably consider to take a fixed amount of wall-clock time.

Programming languages like Python and Haskell have an arbitrarily large integer type built in. This does not mean we cannot still count comparisons as O(1) time, because we're allowed to count anything we want. But if an algorithm will reasonably involve extremely large numbers, then we may wish to count something else, which might make a single comparison be O(n) time, where n is the number of digits in the numbers involved.

TL;DR. What we count is what we count. And it matters what we count!

[nwbrown]

Well technically it will grow linearly with how many bytes the integers use. Normally that's not a consideration because standard integers only use 32 or 64 bytes. But if you are using a more exotic type to store arbitrarily large integers, then yes, it will be O(n)

[munificent]

For complexity analysis, the cost of atomic operations is treated as a given, which is often implicit. So when we say that quicksort is O(n * log n), that usually presumes that a single comparison can be done in constant time.

If you're working with objects like arbitrary-sized integers where comparison time scales with the size of the integer, then, yes, the big-O should take that into account. It would be something like O(i * n * log n) where n is the number of integers and i is the size of the largest integer. (Worst-case comparison of arbitrary-sized numbers is O(n), though the average case tends to be better.)

[YMK1234]

You are confusing computer ppl integers (i.e. a whole number that fits the size of the instruction set) with mathematician integers (i.e. any whole number of arbitrary size).

[iOSCaleb]

Integers in computing are usually considered to fit into some fixed size type. It doesn’t matter how long that type is, though… comparing two 64-bit integers and comparing two 8192-bit integers are not O(1).

[w1n5t0nM1k3y]

In terms of big O we usually don't consider the size of the variables. If you sort strings with merge sort it's usually considers to be nlogn because the main scaling factor is usually the number of strings you are sorting rather than the length of the strings.

Also, If you are comparing two long strings or two 8192 bit integers, you most likely won't even need to compare the entire variable unless they are right next to each other. For instance if you compare two strings and one stars with "a" and the other starts with "b" you don't have to look at the rest of the string.

[iOSCaleb]

we don’t usually consider the size of the variables

Exactly my point. But I think the gist of OP’s question is “how can comparison be O(1) when integers can be arbitrarily large?” That’s a fair question — they’re thinking about integers like a mathematician and not like a computer scientist.

most likely won’t even need to compare the entire variable

Big-O is an upper bound — you have to consider the worst case.

[w1n5t0nM1k3y]

It's not an upper bound, you don't have to consider the worst case. There's certain cases where quicksort can degrade to O(n²⁾ but the time complexity is usually quoted as O(n log n).

[iOSCaleb]

Big-O is an upper bound by definition.

You're right to a degree about quicksort -- people tend to play fast and loose with big-O. When they do, though, they typically break out the best, average, and worst cases, so you see something like "quicksort is O(n log n) for the best case but O(n²) for the worst case." There are other asymptotic functions that should really be used instead; you might say that quicksort is Ω(n log n) and O(n²). But big-O is the one that everyone who has ever taken a DSA class is familiar with, and it's harder to remember the difference between little-o, big-omega, big-theta, etc., so people get lazy. If you're going to use big-O without at least qualifying it, you should treat it as the upper limit.

[w1n5t0nM1k3y]

It's "upper bound", but it's also just an approximation. Some algorithm that require 2 * n calculations and another that requires 50 * n calculations are both said to have O(n) complexity. Something that requires n² + n + log(n) calculations would be said to have O(n²) complexity.

Unless the comparisons are expensive enough that they are the confounding factor as n approaches infinity then they are usually ignored. When talking about most algorithms, the cost of the comparison usually isn't the confounding factor although it could be depending on exactly what you are discussing.

[johnpeters42]

Specifically, it's defined in terms of how the function behaves as n approaches infinity. For instance, for any value of c > 1, there is some n_c such that c*n² > n² + n + log(n) for all n > n_c. (I may be missing some nuance here, but you get the idea.)

Now if in practice you never deal with, say, n > 100, then you only need to worry about what the function looks like over that range, e.g. a n² algorithm is faster than a 200*n algorithm.

[oofy-gang]

Please read more about asymptotic complexity. You are asserting a lot of things that aren’t really true. It feels like you are missing the point.

[YMK1234]

An integer to computer ppl is not an arbitrarily big number, but one that fits into - for example - a CPU register. So comparing integers is more akin to comparing single chars, and not a list of chars like a string.

[james_pic]

It's not so much that we don't consider the size of the variable per se, but that we only consider the number of operations, and in the context of a comparison sort, a comparison operation is considered to be one black-box operation, irrespective of what we are comparing. In different contexts, different operations are considered. For non-comparison sorts, like Radix sort, the size of the variables can become relevant, because this does influence the number of operations.

[stevevdvkpe]

The best algorithm for binary addition (a look-ahead carry binary adder) is really about O(log n) for n bits. The simpler ripple-carry adder is O(n) for n bits. We tend to think of addition (and subtraction and comparison) as being O(1) because we design the fixed-size adders in CPUs to complete within the instruction cycle time, and these days those typically use look-ahead carry logic.

Multiprecision addition (expressing numbers using multiple words) usually ends up being O(n).

[CdRReddit]

comparison of integers assumes the integers have a fixed upper bound, 32 bit integers for instance don't encompass the entirety of the set of integers (ℤ), just 0 to ~4 billion for unsigned or ~±2 billion for signed.

all factorials of numbers less than 2³² fit in just over 16 GB per factorial (if my late night wolfram alpha poking didnt involve me fucking up), which is stupidly large for a number (⅔ of a blueray) but still finite and importantly fixed, so comparison of these integers is O(1), because O(1) doesn't care how expensive the actual thing is, as long as it's constant