On Sep 14, 2010, at 10:37 AM, Jos Koot wrote: > The following measurement shows O(n). > But O(n) = O(C+n) where C may be a big number.
More relevantly, O(n) is hard to distinguish experimentally from O(n log n). In particular, all the sizes you seem to tried are well within a machine word, so I would expect O(n) behavior in that region (for reasons that other people have already pointed out). Big-O notation is about what happens _in the long run_, as you "approach infinity". Any experimental analysis will only tell you about a finite region, so it can't confirm or deny any big-O estimate. Of course, if your "finite region" covers all the problem sizes you will ever realistically want to solve, then an experimental analysis is actually more informative than a big-O estimate. Stephen Bloch sbl...@adelphi.edu _________________________________________________ For list-related administrative tasks: http://lists.racket-lang.org/listinfo/users
