On Mon, Aug 20, 2012 at 10:09 AM, Chris Angelico <ros...@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). -- http://mail.python.org/mailman/listinfo/python-list