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
n is the length of the shortest string.
However, comparing two numbers for equality is
Why is that? Wouldn't the interpreter have to iterate through every number to check for equality?
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
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).
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.
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 ;-)
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.
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.
n can indeed get arbitrarily large*, so we say the comparison takes
*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.
©2020 All rights reserved.