On Saturday 13 December 2008 14:29, levand wrote: > > ... > > > Calling reverse when done is still O(N) > > Really? Maybe my grasp of big-O notation is faulty, but isn't the > recursive function itself O(n), and then a reversal another O(n) > operation on top of that, leading to two complete traversals of the > source list? I thought it was impossible to do a reversal on a linked > list in constant time. Or is the implementation actually doubly- > linked?
Any algorithm that requires to O(n) steps is itself O(n). The big-O concept is roughly "equality up to a constant factor." > Thanks for the reply, Rich! I am really impressed by what you've done > with Clojure. > > -Luke Randall Schulz --~--~---------~--~----~------------~-------~--~----~ 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 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 -~----------~----~----~----~------~----~------~--~---
