If anyone is interested in hearing what's wrong with that post, please ask and I will explain. Otherwise, I won't waste my time.

That's not a very useful response. If you have an objection to my post - please elaborate since otherwise we can't really discuss it. And that's the point of a forum, to discuss things - isn't it?

Or would you like me to guess why you disagree?

It isn't true that Big-O = worst case, Big-Omega = best case, and Big-Theta = average case.

Big-O = upper bound. We are often interested in an upper bound on the worst case so it gets associated with worst case behavior, but we are also often interested in an upper bound on average case behavior, etc.

Hmm.. You're right - I should have used upper bound, lower bound etc instead of worst case, best case etc.

And on more complex algorithms with very complicated behaviour I can see how we'd want to consider the upper bound on the average behavior etc.

I'm still not entirely convinced that using Big-O in such a manner is the best approach, but at least the way you explained it seems mathematically sound.

If anyone is interested in hearing what's wrong with that post, please ask and I will explain. Otherwise, I won't waste my time.

That's not a very useful response. If you have an objection to my post - please elaborate since otherwise we can't really discuss it. And that's the point of a forum, to discuss things - isn't it?

Or would you like me to guess why you disagree?

Well, I started writing a long text about what big-O notation means, how it describes a bound on functions and says nothing about what the functions mean. Then I was going to go into how those functions could be the average time taken for inputs of length n, or the maximum of the times taken for inputs of length n, or they could be measuring space instead of time, or stack space, or anything else.

But I was coming up with a complicated mess and I didn't know if anyone was going to read it, since you, hikarihe and NightCreature83 didn't seem to be listening and perhaps nobody else was reading by now. But I think jwezorek did a great job of figuring out what the misunderstanding was.

So basically when you were saying "worst-case" you mean "upper bound" (which are not the same thing at all), and that confused the hell out of me.

In short: In CS Big-O notation is used for worst-case running time, for average-case running time, number of comparisons, number of swaps, number of floating-point multiplications, or for any other relevant metrics of the performance of an algorithm as a function of the length of the input. In all cases what is being expressed is an upper bound.

With that in mind, now look at how weird your posts, hikarihe's and NightCreature83's look.

I just skimed through the posts and I think all the important things have already been said.
But there is one thing which bothers me, always had and always will. Formally it is not correct to write
f(x)=O(n)
for example. O(n) is a set of functions and therefore f(x) can only be an element of this set. One should write

[eqn]f(x)\in O(n)[/eqn]

I just skimed through the posts and I think all the important things have already been said.
But there is one thing which bothers me, always had and always will. Formally it is not correct to write
f(x)=O(n)
for example. O(n) is a set of functions and therefore f(x) can only be an element of this set. One should write
[...]

It's an abuse of notation. The way big-O notation is used in CS, I think this abuse of notation doesn't contribute anything and we would be better off if people instead used the set notation.

But consider this formula:
[eqn]e^x = 1 + x + {x^2 \over 2} + o(x^2)[/eqn]

What that really means is that
[eqn]e^x - (1 + x + {x^2 \over 2}) \in o(x^2)[/eqn]

But the first way of writing it is much easier to read: The exponential of x is one plus x plus x squared over 2 plus something that grows slower than x^2.

[EDIT: [eqn] seems to be broken, but hopefully you can read through the mess].

But the first way of writing it is much easier to read: The exponential of x is one plus x plus x squared over 2 plus something that grows slower than x^2.

I agree that the first formula is easier to read when you know what this means, but when I started learning the big O notation and set theory the first formula was still a bit confusing in the beginning. I always tended to write it like this:
[eqn]e^x = 1 + x + {x^2 \over 2} + g(x), g(x)\in o(x^2)[/eqn]

It was much clearer especially at the beginning, but it is longer and thus my CS professor abused the notation due to laziness.

I think the best example of that is triangulation:

Triangulating a polygon 'can' be done in O(n) time, but the algorithm to do this is so incredibly complex that unless you have a polygon with 100000000000000 (*number pulled out of my arse) vertices, an O(n.log(n)) or O(n^2) algorithm is going to do it faster.