Ah, ok... I would have assumed that would be labeled as O(2n). Didn't realize that was rolled into the constant factor. So, when graphed, ANY linear function is O(n), no matter how "steep" the line is?
Obviously I have some reading to do. Thanks for the clarification, -Luke On Dec 13, 6:35 pm, Randall R Schulz <rsch...@sonic.net> wrote: > 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 -~----------~----~----~----~------~----~------~--~---
