[racket] Looking for feedback on code style

From: Stephen Bloch (sbloch at adelphi.edu)
Date: Tue Sep 14 10:56:32 EDT 2010

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

Posted on the users mailing list.