Abuse of Big Oh notation

[Chris Angelico]

On Tue, Aug 21, 2012 at 2:01 AM, Paul Rubin <no.email at nospam.invalid> wrote:
> Analogy: how big a box is required to hold a pair of shoes?  In a purely
> theoretical sense we might say O(S) where S is the shoe size, treating
> shoe size as an arbitrary independent variable.  But in the real world,
> shoe size is controlled by the size of human feet, which is bounded by a
> constant for biological reasons.  You don't have to consider shoes the
> size of Jupiter.  So it is O(1).

By that argument, everything is amortized O(1), because there's a
limit on every variable. You can't possibly be working with a data set
greater than the total sum of storage space in the entire world. That
still doesn't mean that bubble sort and heap sort are equivalently
efficient.

ChrisA