On Sunday 14 December 2008 09:00, harrison clarke wrote: > 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.
To be sure. And there can be times that, for the problem size you know you need to handle, an algorithm with better asymptotic behavior is beat by one with worse asymptotic behavior just because of the constant factors in the execution of the "inferior" algorithm. But overall, there are distinctly fewer cases where you don't care about the asymptotic order of the algorithm: linear vs. polynomial; polynomial of degree n vs. polynomial of degree m > n; polynomial vs. exponential; and so on. I seem to recall hearing of a polynomial-time factoring algorithm that was discovered a few years ago. But the degree of the polynomial was something insane: many tens, if I remember correctly. 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 -~----------~----~----~----~------~----~------~--~---
