Big-O notation

[Erik Max Francis]

Peter van Kampen wrote:

> 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)?

It's just mathematics.  You look at the behavior of the algorithm or
data structure as the number of elements gets very large (in order to
drown out fixed-cost or second-order effects).

> for example
> 
> bigO_N(i):
>     for n in xrange(i):
>         print n
> 
> Would be O(N) right?

That's right.  It iterates over each element, and that takes O(n).

> 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.

That's right also.  You're looking at the case where the number of
elements being processed -- even if there are multiple different sets --
grows large.  In this case you're iterating over two lists, but for each
list you're iterating over the other, so as i, j -> oo the behavior is
O(n^2).

> 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(??). 

But there is always some set of behaviors that are core to the
algorithm, and that's what you look at as the number of elements goes to
infinity.  Bubble sort is O(n^2), but quicksort is O(n ln n).

One also often speaks of worst case and average cases (this ties into
what people mean by "amortized O(f(n))" behavior).  For instance, take
finding an element in a sorted binary tree.  The average case is O(ln
n), but the worst case (if the tree is maximally uneven) is O(n).

Adding an element to the end of a dynamically resizing vector is average
case O(1), but worst case O(n), but since this worst case happens on
average n times, we call it "amortized O(1)" behavior.

The big-O notation is one of those things that's really highly
mathematical (particularly if you want to talk about things rigorously),
but it's also something that's vitally important for even novice
programmers to understand very well when they're using algorithms to
solve complex problems that need to be scalable.

-- 
 Erik Max Francis / max at alcyone.com / http://www.alcyone.com/max/
 __ San Jose, CA, USA / 37 20 N 121 53 W / &tSftDotIotE
/  \ The only source of knowledge is experience.
\__/ Albert Einstein
    Bosskey.net / http://www.bosskey.net/
 A personal guide to online multiplayer first person shooters.