Complexity of vector comparison

Question

A question on SO about complexity of sorting vectors of vectors got me thinking about the complexity of comparing 2 vectors.

Let's consider vectors of average size ¹⁾ N.

The first formula we get for the comparison of 2 vectors is O(N), but my intuition says it could be lower. Worst case scenario is N comparisons (vectors are equal), but best case scenario is 1 comparison (vectors differ by first element). Obviously the range of values held is very important here. A vector of 64 bits integers (domain of 2^64 values) is much much more likely it will end the comparison early on than say a vector of 1s and 0s (domain of 2 values).

Let M be the size of the domain (number of values each element can hold; the size of the alphabet)

Now when we consider that M is fixed (which it is) we might be tempted to say that the complexity is still O(N), no matter how large M is. It may have a very small factor O(f*N), but it is still O(N). Mathematically we consider the greatest power in the polynomial. Intuitively a large enough N will hide the factor (which is the probability of 2 elements being equal, or a product of probabilities, correct me if I am wrong).

But... in real life (computation real life) a vector doesn't have unbounded size. A 64 bits integers vector of size 2^64 (N = M = 2^64) would need about 10^8 terra and even a 32 bits integers vector of size 2^32 (N = M = 2^32) would require 16 giga. So I would say it is safe to assume ²⁾ that N < M: the size of the vector is less, much more less than the size of the alphabet.

(for me, intuitively that means that the time complexity doesn't get the chance to "explode" because of the very small factor and because N doesn't get the chance to get sufficiently big - compared to M)

So considering N < M does this mean that for a large fixed alphabet (e.g. 2^32 or 2^64) we can recompute the complexity of vector comparison to something lower than O(N)?

Or am I way off?

---

¹⁾ size of vector = number of elements (not size in bytes)

²⁾ for vectors of large ints and for most real life uses (completely ignoring the rare applications that deal with very very large vectors)

extra) I think it goes without saying that element comparison is O(1)

Answer 1

Normally, in asymptotic analysis, it's most typical to analyze the worst-case running time. It is correct to say that the worst-case running time of comparing two $N$-vectors is $\Theta(N)$; and not any less.

However there's nothing saying you have to focus on worst-case running time. For instance, perhaps you are interested in the average-case running time (also known as expected running time). In this case the answer will be $\Theta(1)$ if we assume that the vectors are uniformly distributed, as you predicted.

However average-case running time is tricky. The expected running time depends on the distribution of values, so you must specify a distribution before you can begin the analysis. If the distribution isn't uniform, then the expected running time might be very different.

Also the expected-running time doesn't add up like you might think. What happens if you run Quicksort on a list of vectors? Can we say that Quicksort does $\Theta(n \log n)$ comparisons on average, and each comparison takes $\Theta(1)$ expected time, so Quicksort on a list of vectors will take $\Theta(n \log n)$ time? No, that doesn't follow. Quicksort will tend to move similar vectors closer to each other, so as you get to later stages in the algorithm, it's possible that you might be mostly comparing vectors that are similar to each other. In particular, the two vectors you're comparing won't be uniformly distributed; they'll come from some joint distribution which tends to make similar vectors more likely. Of course similar vectors are (on average) slower to compare than independently uniformly-random vectors, so there's no longer any guarantee that every comparison takes $\Theta(1)$ time on average.

So, average-case running time analysis can be a lot trickier to get right than worst-case running time. Beware!