> Comparing two strings for equality is linear time on the length of the
> strings.
Not necessarily. If most of the comparisons return false, it may be a lot better than linear. It’s likely in many cases that the comparison will start by comparing the string lengths, so you might get the fastest comparison on average by having the lengths highly variable.
But who says it’s string comparison that dominates? It might be the effect on network latency, or the cost of doing compression. You need to make measurements to find out.
Michael Kay
Saxonica
