It's nonsense to determine O experimentally -- it's too easy for a constant or linear term to dominate a log term over all testable values. For example, you can sort integers in O(n) if you assume that there's an upper bound (for example, 64-bit integers). I had a bit of a red face while trying to convince a Cray programmer that sorting was inherently O(n log n) -- he just kept pointing at his sort function which obviously had O(n) performance. And of course, he's right -- he can sort any useful set of integers in O(n) time. Doesn't change the fact that sorting is, mathematically, O(n log n).
"In theory, there's no difference between theory and practice."
![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png)
timeasmymeasure
no subject
Date: 2004-04-03 08:08 am (UTC)"In theory, there's no difference between theory and practice."