yep. a function f(n) is O(n) if there are constants c and n0 such that f(n) <= c * n for all n >= n0.
sometimes you do care about the c and the n0, though. On Sun, Dec 14, 2008 at 12:41 PM, levand <luke.vanderh...@gmail.com> wrote: > > 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 -~----------~----~----~----~------~----~------~--~---
