So, that's the notation that you often see

throughout the literature describing the performance of algorithms.

But as I mentioned, big O-notation is dangerous,

and I'll have more to say about that in just a minute.

So it's not scientific to use the big O-notation to try to compare algorithms.

If you say the running time is big O(N to the c),

that's not of any use for predicting performance.

It's an upper bound on the worst case.

The actual performance may be much better than the worst case.

And it could be that even the actual bound is less than what’s given

by the big O-notation.

It's fine for a first cut of classifying algorithms, but not useful for comparing.

What we use instead is what’s called the tilde-notation, and so

what we'll typically say is the running time of an algorithm is ~,

a constant, times, say, some function of N, where N is the input size.

That does provide an effective path for predicting performance, and

I'll show some examples of that later on.

So we don't use the common big O, big theta, omega notation very much,

except in a specific technical sense that I'll talk about later on,

when we talk about asymptotic approximations.

So [COUGH] big O-notation is useful for a lot of reasons,

and it dates back a few centuries, and we do use it in math.

But it's a common error to thing that the big O-notation is useful for

predicting performance.

And I just want to make sure to nip that problem in the bud right away.

So this is what often happens to me when I give talks around the world on this topic.

Typical exchange in, say, the Q&A for my talk,

depending on how formal it is, I'll say okay,

big O notation is dangerous, you can't use it to predict performance.

And somebody will ask or shout out, but

an algorithm that is big O(N log N) surely beats when it's big O(n squared).

And then I trot out and say the quick sort, merge sort example and say well,

not by the definition, big O is just an upper bound on the worst case.

And then they'll say, well, so use the theta notation,

which says that it's in-between.

And I say well, that maybe gets rid of the upper bound,

but you're still typically bounding the worst case.

Is your imput a worst case?

And even with that logic and we've got a compelling example like quick sort versus

merge sort, usually what happens is the questioner whispers to one of his

colleagues well, I'd still use the N log N algorithm, wouldn't you?

[LAUGH] And actually, such people usually don't program much and

shouldn't be recommending what practitioners do.

But surely, we can do better than this.

That's part of what analytic combinatorics is all about.

There's another idea that's out there as well, and

that's the concept of a galactic algorithm.

And I found this on a friend's blog, Dick Lipton,

who said let's define an algorithm that will never be used as being galactic.

And why will it never be used?

Because no one would ever notice any effect about this algorithm in

this galaxy.