Home Original page

Abuse of Big Oh notation

Chris Angelico rosuav at gmail.com
Mon Aug 20 12:09:18 EDT 2012 
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
More information about the Python-list mailing list