How to demonstrate bigO cost of algorithms?

Rusty Shackleford rs at overlook.homelinux.net
Wed Jun 2 17:40:12 CEST 2004


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.

-- 
Give and take free stuff: http://freecycle.org



More information about the Python-list mailing list