Reply to thread

Message: [QUOTE="Johannes Bauer, post: 5047890"] Wrong, at least for randomized strings (i.e. every character with the same probability). O(N) is worst-case, O(log N) is correct for randomized strings. Then again, since you were nitpicking about Landau notation earlier this thread, every function bound by O(log N) is also bound by O(N), since, as you correctly stated, it's only a upper bound. We should be talking about the asymptotic sharp bound, i.e. capital Theta. Yes, worst-case is O(N), best case O(1). Average is O(n log n). Best regards, Johannes -- 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> [/QUOTE]