Abuse of Big Oh notation

[Ian Kelly]

On Mon, Aug 20, 2012 at 10:09 AM, Chris Angelico <rosuav at gmail.com> wrote:
> 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.

The difference between the two is that the former is bounded by a
constant that is fundamental to the algorithm at hand, whereas the
latter is bounded only by available resources.  By any practical
consideration the latter must be considered a variable, but the former
need not be.

Paul discusses above the asymptotic growth of a variable as O(S) where
S is shoe size, but really this measure makes no sense in the first
place.  The question that this notation seeks to answer is, "What is
the big-Oh behaviour of this variable as shoe size increases
indefinitely (i.e. to infinity)?" and the answer in this case is "Shoe
size does not increase indefinitely"; the question is invalid.

A more logical question might be, "How much material do I need to
construct N shoes of size S?"  The answer to this question would
presumably be some constant factor of N * S**2, which is O(N * S**2).
Although N can be assumed to vary freely (up to nonsensical quantities
like the mass of the entire universe), S is clearly bounded by the
constraints of actual shoes, so we can safely treat S as a constant
and call it O(N).