[racket] Looking for feedback on code style

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
sbloch at adelphi.edu