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...@speranza.aioe.org> -- http://mail.python.org/mailman/listinfo/python-list
