Path: csiph.com!usenet.pasdenom.info!aioe.org!news.stack.nl!newsfeed.xs4all.nl!newsfeed6.news.xs4all.nl!xs4all!post.news.xs4all.nl!not-for-mail
MIME-Version: 1.0
In-Reply-To: <CAPTjJmqJiGgntZ3bF8Gzt5CtJx7=pzgaKP480w8unjaBd67LQg@mail.gmail.com>
References: <f801e06f-f7b2-4aca-b352-66856a939746@googlegroups.com> <308df2af-abe7-4043-b199-0a39f440e0ab@googlegroups.com> <502f8a2a$0$29978$c3e8da3$5496439d@news.astraweb.com> <7xehn4vyya.fsf@ruckus.brouhaha.com> <5030832d$0$29978$c3e8da3$5496439d@news.astraweb.com> <7x8vdbmho6.fsf@ruckus.brouhaha.com> <mailman.3511.1345397678.4697.python-list@python.org> <7xfw7ilqnd.fsf@ruckus.brouhaha.com> <50314968$0$29978$c3e8da3$5496439d@news.astraweb.com> <7xwr0ua1pw.fsf@ruckus.brouhaha.com> <mailman.3547.1345451405.4697.python-list@python.org> <7xr4r1pn72.fsf@ruckus.brouhaha.com> <CAPTjJmqJiGgntZ3bF8Gzt5CtJx7=pzgaKP480w8unjaBd67LQg@mail.gmail.com>
From: Ian Kelly <ian.g.kelly@gmail.com>
Date: Mon, 20 Aug 2012 11:12:22 -0600
Subject: Re: Abuse of Big Oh notation
To: Python <python-list@python.org>
Content-Type: text/plain; charset=ISO-8859-1
Precedence: list
Newsgroups: comp.lang.python
Message-ID: <mailman.3567.1345482779.4697.python-list@python.org>
Lines: 35
NNTP-Posting-Host: 2001:888:2000:d::a6
Xref: csiph.com comp.lang.python:27510

On Mon, Aug 20, 2012 at 10:09 AM, Chris Angelico <rosuav@gmail.com> wrote:
> On Tue, Aug 21, 2012 at 2:01 AM, Paul Rubin <no.email@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).