On Tue, Jun 23, 2009 at 10:14 AM, Daniel Lyons <fus...@storytotell.org>wrote:
> I have to admit I don't really understand your code, so my apologies if > I've missed something obvious. > > I think if you consider each element of N and do an operation that costs > sqrt(N) with it, you'd arrive at O(N*sqrt(N)), which I think would be worse > than O(N log N) > I guess I must take another coffee, you're right I talked about sqrt instead of log. My bad. > which is what you'd get from just sorting the whole structure and taking > the top n items. Is it really sqrt(N)? I'm under the impression insertion > into a balanced binary tree is O(log(N)), but wouldn't you still need to > have N of them? This algorithm reminds me of heap sort. > The tree never grows beyond (N+1) items, so insertion/deletion is always O(log(N)). But you perform these operations for each item of the full seq, ie nth times (but not Nth times) thus O(n*log(N)) Christophe --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Clojure" group. To post to this group, send email to clojure@googlegroups.com Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en -~----------~----~----~----~------~----~------~--~---
