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 1)
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
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
N = M = 2^64) would need about
10^8 terra and even a 32 bits integers vector of size
N = M = 2^32) would require
16 giga. So I would say it is safe to assume 2) 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)
N < M does this mean that for a large fixed alphabet (e.g.
2^64) we can recompute the complexity of vector comparison to something lower than
Or am I way off?
1) size of vector = number of elements (not size in bytes)
2) 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