How to demonstrate bigO cost of algorithms?

[Phil Frost]

The problem is that BigO cost describes how the computation time scales
with the size of the set, but nothing about how long that really is. For
example, let us implement a trivial algorithm that increments each
number in a list:

def f(list):
  for key in xrange( len(list) ):
    list[key] += 1

this is O(n), because as the size of the set increases, the computation
time increases linearly. Now say we change the implementation to this:

def f(list):
  for key in xrange( len(list) ):
    list[key] += 1
  i = 2**32
  while i:
    print 'wasting time'
    i -= 1

This functionally equivalent algorithm takes much longer to run, but its
complexity is still O(n).

Because O(n) only tells us how the computation time scales, to get the
real time, multiply n by the time it takes to run the algorithm on a set
of size one.

In your case of qsort which is O(log(n)), that is not a base2 log, it's
just a log, and the base doesn't really matter. Changing the base of the
log only multiplies the result by some constant. By simple algebra, we
know that log2(x) = log10(x) / log10(2). From this we can see that
changing the base of the log in your calculation multiplies the result
by a constant. What this constant is depends on the implementation of
the algorithm, and to translate BigO notation into real times you will
have to find it by performing a regression on your data.

That said, BigO notation only gives the complexity in theory, and not
always in practice. Other factors will cause the real run time to
deviate from the BigO model, so you will likely need a large set of data
to clearly see the relation.

On Wed, Jun 02, 2004 at 03:40:12PM +0000, Rusty Shackleford wrote:
> Hi -
> 
> I'm studying algorithms and I want to write a python program that
> calculates the actual runtimes.
> 
> I want to increment up some global variable called n in my program so
> that I can see the relationship between the size of the problem and the
> number of steps.
> 
> Here's my clumsy attempt to implement this:
> 
> def qsort(ll):
>     try:
>         global n
>         n += len(ll)
>         print "adding %d to %d." % (len(ll), n)
>         print "incrementing up n to %d." % n
>     except:
>         pass
>     if len(ll) == 0:
>         return []
>     p = ll[0]
>     left = [x for x in ll if x < p]
>     mid = [x for x in ll if x == p]
>     right = [x for x in ll if x > p]
>     return qsort(left) + mid + qsort(right)
> 
> I'm not getting the results I hoped for.  I expected that after the
> program is finished, I would get results near 
> 
>     len(ll) * math.log(len(ll), 2)
> 
> since the big O for quicksort is nlogn for all but the worst case.
> 
> I'd like to write similar functions for mergesort, bubblesort, and all
> the other basic algorithms covered in data structures classes.
> 
> All help is welcome.