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

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

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

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

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

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

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

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

• javascript
• puter-science
• equality

• 1 What is there to iterate on a number? A number is just the value: 2 for example, is not 3. That's it. Similarly 123 is not 124. A string is a collection of characters "abc" is different to "abd" but you do have to check each character. – VLAZ Commented Oct 28, 2019 at 15:13
• 2 Computers have intrinsic operations that pare entire number values quickly. – Pointy Commented Oct 28, 2019 at 15:13
• 5 If you're working in a language like Erlang with infinite-precision integers, numeric parisons are indeed O(n) – Pointy Commented Oct 28, 2019 at 15:14
• 1 Also instead of "through every number" you probably mean "through every digit" – Pointy Commented Oct 28, 2019 at 15:14
• 1 @Pointy: That would be O(log(n)), because n number's length is proportional to log(n). – Nyos Commented Oct 29, 2019 at 1:30

4 Answers 4

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

Therefore you have a fixed number of bits to pare when paring numbers. It's very easy to build a hardware circuit that pares 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 pare.

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

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, parisons 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 pare.

String

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

The time plexity 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 paring 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 parands).

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 pared until finding the first (if any) mismatching pair. That takes time proportional to the number of digits that need to be pared.

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), bee significant, and can potentially even take over the running time.

With JavaScript strings, n can indeed get arbitrarily large*, so we say the parison 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 parison to occur, and the best systems we have for paring numbers of that exact size more or less run the same regardless of how many of those 64 digits each number actually has - hence, paring 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 parison 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.