What is the expected time complexity of checking equality of two arbitrary strings?

Question

The simple (naive?) answer would be O(n) where n is the length of the shorter string. Because in the worst case you must compare every pair of characters.

So far so good. I think we can all agree that checking equality of two equal length strings requires O(n) runtime.

However many (most?) languages (I'm using Python 3.7) store the lengths of strings to allow for constant time lookups. So in the case of two unequal length strings, you can simply verify len(string_1) != len(string_2) in constant time. You can verify that Python 3 does indeed make this optimization.

Now, if we're checking the equality of two truly arbitrary strings (of arbitrary length) then it is much more likely (infinitely, I believe) that the strings will be of unequal length than of equal length. Which (statistically) ensures we can nearly always compare them in constant time.

So we can compare two arbitrary strings at O(1) average, with a very rare worst-case of O(n). Should we consider strings comparisons then to be O(1) in the same way we consider hash table lookups to be O(1)?

Answer 1

In order to discuss the expected time complexity of an operation, you have to specify a distribution on the inputs, and also explain what you mean by $n$.

One has to be careful, however. For example, consider the suggestion in the comments, to consider some kind of distribution over words of length at most 20. In this case, string comparison is clearly $O(1)$, since 20 is just a constant. There are several ways to avoid it:

• Ask for a non-asymptotic time complexity. Since time complexity is highly dependent on the computation model, you can count (for example) the number of input memory cells accessed.

• You can specify an input distribution which depends on a parameter $m$, and then ask for the asymptotic complexity in terms of $m$.

Here is an example. Given two random binary strings of length $n$, there will be roughly 4 accesses in expectation. In contrast, if the strings are chosen at random from the collection $0^i1^{n-i}$, the number of accesses will be roughly $(2/3)n$. These two distributions can be separated even if we use asymptotic notation: the algorithm runs in $O(1)$ on the first distribution, and in $\Theta(n)$ on the second.

Another issue is the meaning of $n$. Consider for example a string $0^m$, where $m \sim G(1/2)$ is a geometric random variable. When run on inputs of lengths $a,b$, the running time is $\Theta(\min(a,b))$. How should we express this in terms of $n = a+b$? One choice is to ask for the expected running time given that the input length is $n$. In this case, $$ \mathbb{E}[\min(a,b)] = \sum_{a=1}^{n-1} \frac{(1/2)^a (1/2)^{n-1-a}}{\sum_{a'=1}^{n-1} (1/2)^{a'} (1/2)^{n-1-a'}} \min(a,n-a) = \frac{1}{n-1} \sum_{a=1}^{n-1} \min(a,n-a) \approx \frac{n}{4}, $$ so the expected running time is $\Theta(n)$.

Answer 2

In addition to what was said before, consider a modern version of "string" that is fully Unicode compatible. Which means a string is a sequence of Unicode code points, and you can't just compare whether code points are equal, because there are cases where a letter can be represented in different ways, sometimes in many different ways. As an example, the code point sequences (c with cedilla, accent), (c, cedilla, accent) and (c, accent, cedilla) compare equal with a correct implementation.

Answer 3

In Addition to what have been said, and independently on the test if the size is equal or not, let's be the following:

1. Let be two strings of same length m over an alphabet $\sigma$.
2. Let $w$ be the word memory. From wikipedia : a word is a fixed-sized piece of data handled as a unit by the instruction set or the hardware of the processor. In Theory, if we have $n$ elements (in random-access machine (RAM) model), the word length $w =\Omega(log n)$:

• Each character needs $log \sigma$ bits.
• $m$ characters need $m log \sigma$ bits
• To compare two strings of length $m$ we need $m log \sigma / w$ which gives us $O(m log \sigma / w)$.

Clarification:
Normally (and Naively), we check one char at the time, which gives $O(m)$.
Using advantage of Bit-level parallelism, the processor can handle a data of size $w$ at single time, this, mean to check m characters we need $m/w$ operations.
Example from wikipedia:
For example, consider a case where an 8-bit processor must add two 16-bit integers.The processor must first add the 8 lower-order bits from each integer, then add the 8 higher-order bits, requiring two instructions to complete a single operation. A 16-bit processor would be able to complete the operation with single instruction.

In practice, An illustrating example:

• in $64$ bits machine
• using C language, where sizeof(char) = 1 Byte which is $8 bits$
• For $m = 8$ characters, which means $8\times8 = 64$ bites

Here, naively, if we check each char alone , we need 8 operations. If we take advantage of Bit-level_parallelism, where the processor can handle 64 bits at the time, so we need only one operation ($ len(str)*size\_char\_bits / w\_in\_bits = 8 chars * 8 bits / 64 bits = 1$)

important note: this is just to check if the two string are equal or not.

Edit one info: Correct some mistakes. Thank you @greybeard, for your valuable comment.