Path: csiph.com!newsfeed.hal-mli.net!feeder3.hal-mli.net!newsfeed.hal-mli.net!feeder1.hal-mli.net!newsfeed.xs4all.nl!newsfeed6.news.xs4all.nl!xs4all!post.news.xs4all.nl!not-for-mail
Return-Path: <rosuav@gmail.com>
X-Original-To: python-list@python.org
Delivered-To: python-list@mail.python.org
X-Spam-Status: OK 0.015
X-Spam-Evidence: '*H*': 0.97; '*S*': 0.00; '21,': 0.07; 'received:209.85.160.174': 0.07; 'argument,': 0.09; 'aug': 0.13; 'size,': 0.13; 'amortized': 0.16; 'biological': 0.16; 'from:addr:rosuav': 0.16; 'from:name:chris angelico': 0.16; 'heap': 0.16; 'subject:Big': 0.16; 'variable.': 0.16; 'wrote:': 0.17; 'sort': 0.21; 'constant': 0.22; 'controlled': 0.22; 'paul': 0.24; 'header:In-Reply-To:1': 0.25; 'am,': 0.27; 'possibly': 0.27; 'message-id:@mail.gmail.com': 0.27; "doesn't": 0.28; 'sense': 0.31; 'to:addr:python-list': 0.33; "can't": 0.34; 'received:google.com': 0.34; 'received:209.85': 0.35; 'but': 0.36; 'received:209': 0.37; 'data': 0.37; 'subject:: ': 0.38; 'mean': 0.38; 'to:addr:python.org': 0.39; 'space': 0.39; 'where': 0.40; 'header:Received:5': 0.40; 'real': 0.61; 'limit': 0.65; 'total': 0.65; 'theoretical': 0.65; 'sum': 0.66; 'bounded': 0.84; 'subject:Abuse': 0.84
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=mime-version:in-reply-to:references:date:message-id:subject:from:to :content-type; bh=REVOoEYxZUEARZcfmm8qAql7R4mMKP7/AExALSVEoQI=; b=Y4RAwIhGumqENJbxjCnibcczZNwE7HreOfnFFID2vOvDFLFjDRnkMW9qJPF3gxwXG5 oAQOU9IOWSxAVHRrViMfkmK9j432bK4BPOAjfDW3QoeWcol7rNB5LVouf4HcgLkXfIrV UyvzyenKZPXgGMl6MjNmCetu6BLUV3D+5VoJX1ehIzM87KbvmDBG6UL7LPbbVjnPzcqj ppJDYOEnSpJ16ckAW89o0mxSKMUXl0tEoxNqGSY/ZkKEphqc6Fi8PTbRkRKDZ077TIfN eQVdsVW70775WyYKnGukvWl1hpRfE6xbYAEYuK7ni6wGgqcUZvYn/VwOSpT+im+BYC+u 5WTg==
MIME-Version: 1.0
In-Reply-To: <7xr4r1pn72.fsf@ruckus.brouhaha.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>
Date: Tue, 21 Aug 2012 02:09:18 +1000
Subject: Re: Abuse of Big Oh notation
From: Chris Angelico <rosuav@gmail.com>
To: python-list@python.org
Content-Type: text/plain; charset=ISO-8859-1
X-BeenThere: python-list@python.org
X-Mailman-Version: 2.1.12
Precedence: list
List-Id: General discussion list for the Python programming language <python-list.python.org>
List-Unsubscribe: <http://mail.python.org/mailman/options/python-list>, <mailto:python-list-request@python.org?subject=unsubscribe>
List-Archive: <http://mail.python.org/pipermail/python-list>
List-Post: <mailto:python-list@python.org>
List-Help: <mailto:python-list-request@python.org?subject=help>
List-Subscribe: <http://mail.python.org/mailman/listinfo/python-list>, <mailto:python-list-request@python.org?subject=subscribe>
Newsgroups: comp.lang.python
Message-ID: <mailman.3563.1345478961.4697.python-list@python.org>
Lines: 15
NNTP-Posting-Host: 2001:888:2000:d::a6
X-Trace: 1345478961 news.xs4all.nl 6860 [2001:888:2000:d::a6]:48900
X-Complaints-To: abuse@xs4all.nl
Xref: csiph.com comp.lang.python:27505

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.

ChrisA