Search code examples
javascriptcomputer-scienceequality

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?


Solution

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