Comparing strings from the back?

[Johannes Bauer]

On 06.09.2012 16:23, Dave Angel wrote:
> On 09/06/2012 09:43 AM, Johannes Bauer wrote:
>> <snip>
>> Yes, worst-case is O(N), best case O(1). Average is O(n log n).
> 
> Can't see how you came up with an average of n log(n).  Fourteen minutes
> before you made this post, you demonstrated it was less than 2 for any N.
> 
> And I previously posted that for a character set of size 10, the average
> was 1.1111

Again playing with the equations and thinking about it again. And I
completely missed your point. It wasn't about n log n vs. log n. Both
are wrong. This surprises me. I was somehow thinking about the limit of
sum (1/n), n -> infty. But since the summands are shrinking
exponentially, the limit is different.

I think the limit of the average comparisons for a given wordlength n
against infinity with alphabet size l is

l / (l - 1)

i.e. for bitstrings it's 2 and for bytestrings it's 256/255.

This would mean string comparison of randomized strings is O(1). Can
that really be true? It looks like it.

Best regards,
Johannes

-- 
>> Wo hattest Du das Beben nochmal GENAU vorhergesagt?
> Zumindest nicht öffentlich!
Ah, der neueste und bis heute genialste Streich unsere großen
Kosmologen: Die Geheim-Vorhersage.
 - Karl Kaos über Rüdiger Thomas in dsa <hidbv3$om2$1 at speranza.aioe.org>