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.
O(log n) is what I meant, sorry! Damnit. > And I previously posted that for a character set of size 10, the average > was 1.1111 For any given string n and and alphabet size l, the average is: sum(i = 0..n) (1 / (l ^ n)) So with larger word length, the total complexity constantly increases. The amount by which it increases however is shrinking exponentially with the word length. Therefore O(log n). Sorry about the n log n mistake, argh. Best regards & thanks for the correction, 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
