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

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)?

• I think it depends on the distribution from which the strings are coming. For example, suppose we are dealing with an application which handles 10 millions users. Most names range in length from 2 to 20, say. Assuming uniform distribution, there would be 0.5 millions collision on 10 million comparisons. Which is sufficient to put this in O(n). – prime_hit Jul 2 '20 at 7:11
• I agree with @prime_hit - But in general big $O$ complexity is reserved for the worst case - not the expected or average case. In other words, the distribution of strings is irrelevant to the upper bound $O$ from a theoretical point of view. – Novicegrammer Jul 2 '20 at 8:42
• @Novicegrammer He is talking about Amortized Complexity. – prime_hit Jul 2 '20 at 9:58
• I think you meant average complexity (average on input distribution) and not amortized complexity (average on function calls in data structure, assuming worst input distribution) – nir shahar Jul 2 '20 at 10:23
• You cannot talk about the expected time complexity until you specify an input distribution. – Yuval Filmus Jul 2 '20 at 11:19

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

• Accepted, thanks, though I am unfamiliar with some of the notation you use in your last two examples. If there is an "explain like I'm five" version I'd be very interested. – jtschoonhoven Jul 3 '20 at 1:00
• I'll attempt an intuitive explanation: to compare any one string of length m against another string of length n, there is a 1/max(n, m) chance that the strings are equal length. If the strings are equal length, then comparing them is linear. So the expected runtime would be O(1/max(n, m) * n) or simply O(n). – jtschoonhoven Jul 3 '20 at 1:22

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.

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.

• Welcome to COMPUTER SCIENCE @SE. If your spelling checker didn't flag wich, it deserves all the bites it hardly could. – greybeard Oct 7 '20 at 7:13
• While "programming" is off-topic, the C sizeof operator does not yield a size in bits, but bytes ; a limits header provides CHAR_BIT (with sizeof(char) 1). – greybeard Oct 7 '20 at 7:19
• Can you simplify $O(m\log \sigma / w)$? – greybeard Oct 7 '20 at 7:21
• @greybeard, Thank you for wishing me welcome :).;and also thank you for valuable comment, indeed I made some mistakes and I correct theme Now. the programing part, is just an illustration. As added in the post above, In RAM Model, if we have n elements, the word $w$ length is $w=\Omega (logn)$. – ibra Oct 7 '20 at 12:53
• @greybeard, The $O(m log \sigma / w$ is already simple, maybe I can explain it more, naively we check one element at time, which result in $O(m)$, using advantage of Bit-level parallelism, the processor can handle a date of size $w$ at time, so number of operation will be $m log \sigma/w$. – ibra Oct 7 '20 at 12:54