2
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ 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). $\endgroup$ – prime_hit Jul 2 at 7:11
  • $\begingroup$ 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. $\endgroup$ – Novicegrammer Jul 2 at 8:42
  • $\begingroup$ @Novicegrammer He is talking about Amortized Complexity. $\endgroup$ – prime_hit Jul 2 at 9:58
  • 1
    $\begingroup$ 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) $\endgroup$ – nir shahar Jul 2 at 10:23
  • 3
    $\begingroup$ You cannot talk about the expected time complexity until you specify an input distribution. $\endgroup$ – Yuval Filmus Jul 2 at 11:19
3
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – jtschoonhoven Jul 3 at 1:00
  • $\begingroup$ 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). $\endgroup$ – jtschoonhoven Jul 3 at 1:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.