Big-O notation

[Peter van Kampen]

In article <mailman.1050457621.2105.python-list at python.org>, Mike C.
Fletcher wrote:
> Andrew Koenig wrote:
> 
> Okay, so now we have "The Practical Coder's Guide to big-O Notation" :) 
> .  We rock ;) ,
> Mike

You do, you know...c.l.p really does.

I think I almost 'get it'. Except who or what decides what Big-O a
certain algorithm has. Is that by 'hunch' or by running benchmarks or
are there still other ways to recognize 'Big-O's (except for the
formal computations that I understand are not very common)? 

for example

bigO_N(i):
    for n in xrange(i):
        print n

Would be O(N) right?

bigO_N2(i,j):
    for n in xrange(i):
        for o in xrange(j):
            print i,j

This would be O(N**2)? Actually O(i*j) I suppose but if i==j N**2
applies.

But these are not really 'algorithms'. Most algorithms are a lot more
complex even when reduced to it's essentials. I understand why
quicksort is better than bubblesort but I don't see an obvious way to
label quicksort O(??). 

PterK

-- 
Peter van Kampen
pterk -- at -- datatailors.com