I don't understand how there can be such a discrepancy between us.

I don't think anyone's arguing that the information you're trying to convey is unimportant. It's just that the means you're using to communicate that information is bad.

The Big-O "toolbox" is designed for for asymptotic analysis where constant overheads and practical performance issues fall out. Therefore it's pretty silly to use this notation to convey information about constant overhead and practical performance issues.

Just add a sentence "in practice, @jonnin's modified skip-list can be about k times faster".
And then everyone would be satisfied.

I don't think anyone's arguing that the information you're trying to convey is unimportant.

I believe that's exactly what they're saying, repeatedly stating there is no information to be obtained from the constant:

My contention would be that the constant is indeed worthless

Therefore it's pretty silly to use this notation to convey information about constant overhead and practical performance issues.

This isn't an argument. I said myself that Big-O doesn't care - that doesn't mean YOU shouldn't. and O(3n) is NOT meaningless, you are losing information by reducing it.

However, in the eyes of Big-O, as n goes to infinity, 3 * n is negligible. As a programmer, somehow I've never worked with a list of near infinite elements - perhaps I'm still new to programming.

Just add a sentence "in practice, @jonnin's modified skip-list can be about k times faster". And then everyone would be satisfied.

That does not satisfy anything - why is it? "Can be"? When is it and when is it not? This solution drives you even further away from a proper solution to the issue.


jonnin provided a very convincing argument. And another argument no one has seemingly tried to answer is the one of Radix Sort: O(n*d). d is just the length of the largest number. You loop by n * d number of times. As n goes to infinity, d can be 1 for all we know.

Radix sort single-handedly shows that a constant is removed for no other reason than it's not directly tied to the input and ... is a constant.

Eh, even I admit that its an abuse of big-O to use it this way.

The problem of trying to describe something like the skip list example ... what choices do you have? Math language (proof symbols, etc), but more often than not fellow coders don't know that well if at all. Natural language is prone to ambiguities. Borrowing heavily from big-O notation works because almost all coders speak it well enough to discuss the point in question, as long as you all understand its NOT really big-O, its just a similar topic that stole the terminology.

You can tighten up the added words, if you want to try the natural language route:
"The skip list is K times faster when the list is larger than K." (and whatever else, its a partial example, not rigor).
I am ok with that too, but borrowing big-O is more compact.

For radix sort.. the implementation choices matter, just like choosing 100 vs 3 matters in the skip list, it has a drastic effect. You can still put that into english, if abuse of big-O with constants is not working for you. I think you can even abstract it out like the K thing above. But some algorithms defy that too: shell sort has completely different run times from N*N to various N to the 1.XXX fraction power to a couple of other run times if you mess with the choices. You can't abstract it out at all, on that one.

zapshe wrote:
> I don't think anyone's arguing that the information you're trying to convey is unimportant. I believe that's exactly what they're saying, repeatedly stating there is no information to be obtained from the constant:

The meaning of O(3n) = O(n) is distinct from the importance of the information O(3n) is trying to convey. Besides I wrote my post assuming the "the information you're trying to convey" is about the performance of a particular algorithm, and I agree that this is important.

That does not satisfy anything - why is it? "Can be"? When is it and when is it not? This solution drives you even further away from a proper solution to the issue.

If the issue is "identify the faster of two algorithms with the same asymptotic complexities", we can still use theoretical tools to help make the decision. But not Big-O, it's unsuitable for this purpose.

For example, we could compare versions of bubble sort:


Some addition shows that v.1 does n(n - 1) comparisons while v.2 does n/2(n - 1) comparisons. We can compare those two expressions and get a meaningful answer without involving big-O at all.

jonnin wrote:
Eh, even I admit that its an abuse of big-O to use it this way.

Abuse of notation - that's the point!

The meaning of O(3n) = O(n) is distinct from the importance of the information O(3n) is trying to convey

I've made this very argument. In terms of asymptotic time complexity, 3n and n are practically the same as n goes to infinity. In terms of a programmer working with algorithms, they are completely different.

Some addition shows that v.1 does n(n - 1) comparisons while v.2 does n/2(n - 1) comparisons. We can compare those two expressions and get a meaningful answer without involving big-O at all

That's the only argument I've ever made. That removing the constants to satisfy Big-O is not what's best for a programmer trying to compare algorithms.

There's nothing wrong with borrowing the notation for your own needs: O(n^2 - n) vs O((n^2)/2 - n/2). These are the worst case scenarios for V1 and V2. There would be a different omega if a condition is added to check for a swap and exit if no swap happens - creating an Ω(n). Would removing O() and Ω() make everyone cream their pants?


To say, "Well you're using Big-O notation which doesn't allow it.. so you're wrong!" is to be emotionally tied down. It's like saying you can't use a wrench as a hammer; you'd be right in some cases, but in general you're just trying to get a nail through.



Other than whether appropriate to use Big-O notation, we seemingly haven't diverged in opinion. However, others, like lastchance, from what I've read are claiming exactly the opposite - that there is NO information to be derived. That Bubble sort written as O(n^2 - n) vs O((n^2)/2 - n/2) cannot be differentiated based off these constants and should both be seen as O(n^2) and call it a day.

In fact, my last debate with Peter was certainly saying that, as he tried to give an example of an algorithm that was O(2n) by dividing the work of an O(n) algorithm between two loops - implying that the constant is meaningless since both programs do the same amount of work (setting aside loop overhead). This is a flawed argument in many ways, but not going to argue with myself here.

> In terms of asymptotic time complexity, 3n and n are practically the same as n goes to infinity.

The Big O notation is only about how the time or space requirements of an algorithm grows with the size of the problem (n here). Not to infinity, but for instance what if n grows by a factor of 10? Is this information useful for a programmer? Yes, often enough, when we know that in production n is going to be quite different; much bigger than the n in our test cases.

Big O does not claim to be a measure of the performance of an algorithm. For that matter, even notations like O(3n) or O((n^2)/2 - n/2) do not provide a measure of its performance. Even on the same hardware family, relative performance between algorithms can vary widely depending on factors like the number and speeds of processors and cache size, amount of memory etc. Some critical factors may not even be predictable: for instance the number and types of other programs running simultaneously, competing for shared resources. Is information about performance useful for a programmer? Yes, often enough. IMHO, for performance one actual measurement is worth more than a dozen mathematical models.

Big O is also not an indicator of how easy or difficult it is to write, test, and debug code for the algorithm. Is this information useful for a programmer? Yes, certainly.

Big O does not claim to be a measure of the performance of an algorithm

Indeed-y. I've said before but which has been lost in the flood of debate, that in the end, you have to time it and see for yourself. Even that isn't perfect with different CPU designs and different operating systems.

If I'd of gotten attacked by JLBorges too I'd of cried.

However, others, like lastchance, from what I've read are claiming exactly the opposite - that there is NO information to be derived. That Bubble sort written as O(n^2 - n) vs O((n^2)/2 - n/2) cannot be differentiated based off these constants and should both be seen as O(n^2) and call it a day.

That's just a consequence of the definition of big-O. A literal reading of the math.

There's nothing wrong with borrowing the notation for your own needs: O(n^2 - n) vs O((n^2)/2 - n/2).

I disagree. The statement "this algorithm makes O((n^2)/2 - n/2) comparisons" is different from "this algorithm makes (n^2)/2 - n/2 comparisons". So why say the first statement when you mean the second?

Otherwise we're in agreement.

That's just a consequence of the definition of big-O. A literal reading of the math

I'm fairly certain this is not the argument put forth by lastchance, and especially not Peter. I clarified several times that it's against Big-O and that's fine for when using Big-O, but that we as programmers can benefit from the knowledge. His argument was centered around the idea that those numbers are fundamentally meaningless, not just meaningless in the context of Big-O.

I disagree. The statement "this algorithm makes O((n^2)/2 - n/2) comparisons" is different from "this algorithm makes (n^2)/2 - n/2 comparisons". So why say the first statement when you mean the second?

Such a small disagreement is hardly worth debating. But my reasoning for using the notation is simply expediency. People will understand O(3n) is worst case and Ω(n) is best case without having to explain yourself.

In Big-O terms, if complexities were O(3n) and Ω(n), you'd simply say Θ(n) - best and worst case are the same. Having a constant makes it clear we did Big-O minus simplifying.

I'd assume most would be able to just intuitively understand that Big-O notation is being used, but with laxed rules for the benefit of information.


That is just my opinion and there's not much to be gained from arguing preferences. The real argument I've been making is in the realm of facts, whether the constant is meaningless or not.

Never mind, @zapshe, you can go on writing O(3) while the rest of us write O(1).

Don't worry, I don't use Big-O anyway. I prefer Big Mama