Why is comparing strings 0(n), but comparing numbers 0(1)?

I understand that to compare two strings for equality, the interpreter has to iterate through both strings and compare each character.

That would make the time complexity 0(n) where n is the length of the shortest string.

However, comparing two numbers for equality is 0(1).

Why is that? Wouldn't the interpreter have to iterate through every number to check for equality?

Answers:

Answer

Numbers in computers are usually handled in fixed-size units. A int might be 32 or 64 bits in any given language and/or compiler/platform combination, but it will never be variable-length.

Therefore you have a fixed number of bits to compare when comparing numbers. It's very easy to build a hardware circuit that compares that many bits at once (i.e. as "one action").

Strings, on the other hand, have inherently variable lengths, so you just saying "string" doesn't tell you how many bits you'll have to compare.

There are exceptions however, as there are variable-length numbers, usually called something like BigInteger or BigDecimal which will behave very similar to String comparison as it might end up being O(n) to compare two BigDecimal values for equality (where n is the length of the BigDecimals, not either of their numeric values).

Answer

Usually programs represent numbers as fixed-sized data structures (binary values, which is why you may see their sizes described in bits). Being fixed-size, comparisons would take a constant amount of time and be O(1), which is one of the benefits of such a representation. A downside would be a limit on the range of values that can be represented.

An alternate representation that lifts this restriction, allowing for an arbitrarily-large range of numbers, would thus no longer be fixed in size, and no longer be O(1) to compare.

Answer

String

String comparisons are typically a linear scan of the characters, returning false at the first index where characters do not match.

The time complexity is O(N) and the actual time taken depends on how many characters need to be scanned before differences statistically emerge. There isn't a simple answer, but the answer is nevertheless obvious ;-)

Numbers

if two integers are in equal, it's impossible to know 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 many cases, all relevant 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 are 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.

Answer

In general, we only use big-O notation when n can rise to obscenely large values, because big-O notation describes how the execution time grows as the input grows. For instance, when sorting a list, most of the best algorithms sort in O(n log n) - which means, and only means, that when the list is long enough, that the time it takes to sort it is proportional to n log n. When the list is not long enough, other factors (for instance, any time your algorithm might take to allocate extra space), become significant, and can potentially even take over the running time.

With JavaScript strings, n can indeed get arbitrarily large*, so we say the comparison takes O(n) time. But with JavaScript numbers (which are IEEE 754 double-precision floating point numbers), n has a maximum cap of 64 - 1 for a sign bit, 11 for an exponent, and 53 for significant digits**. Because of this, we know exactly how long it will possibly take for a number comparison to occur, and the best systems we have for comparing numbers of that exact size more or less run the same regardless of how many of those 64 digits each number actually has - hence, comparing these numbers in JavaScript is considered O(1).


*Technically, there is an upper limit because RAM can run out. However, the language doesn't specify a maximum size for strings, and the O(n) part of string comparison dominates the execution time well before that happens.

**By the way, this does mean that numbers in JavaScript can't rise infinitely. Past a certain point, they start throwing away smaller digits (for instance, numbers above 2^53 can only be even, and numbers above 2^54 can only be divisible by 4), and when the number gets large enough, it rounds up to infinity. Conversely, if you divide a number over and over again to make it infinitesimally small, it will eventually round down to zero.

Tags

Recent Questions

Top Questions

Home Tags Terms of Service Privacy Policy DMCA Contact Us

©2020 All rights reserved.