I find this a too informal and ultimately confusing.
> Misconception 1: “The Equals Sign Means Equality”
The equal sign does mean equals.
> The left-hand-side is a function, the right-hand-side is a … what, exactly? There is no help to be found in the definition. It just says “we write” without concerning itself with the fact that what “we write” is total nonsense.
This is not clear at all !
> If you take it at face value, you can deduce that since 5n and 3n are both equal to O(n), then 3n must be equal to 5n and so 3=5.
Yes well, f(x) = f(y) does not implies x = y. I think people know this ..
He is using 'type check' to point out the flaw. x = y means x and y are the same thing. If x is a function and y is an integer, then it can't possibly hold that x = y.
Consider x = O(n). The implication would be that whatever type of thing O(n) is, x also is. This is trivially untrue.
If x = y, and x is a function, then x(K) = y(K). It would be ridiculous to say that x(K) = O(n)(k).
> Yes well, f(x) = f(y) does not implies x = y. I think people know this ..
I don't understand why you are mentioning that. The issue is that x = f(z) and y = f(z), then x = y. You can't get two different values by applying the same function to the same value.
Saying that f is O(n), the "is" is not an equality statement at all, "is" is some other function exactly as you mention that people understand. It is clearly some function that is non-transitive.
In this case the relationship is most easily expressed using existing operators by having O(n) be a set of functions and the "is" in that sentence be the "exists-in" set operator, which is a case where the transitive property doesn't hold. Using the = symbol in that context is just bizarre when = is a otherwise always used to mean equality, which is function with special properties that don't apply here.
In the particular case of big-O notation, the equals sign does not mean equals. Trying to parse the equal sign literally leads to confusing and contradictory interpretations (which is why their explanation is confusion).
You're misunderstanding the 3=5 example. Let f(n)=3n, let g(n)=5n. Using big-O notation, f(n)=O(n), g(n)=O(n). Were the equal sign behaving normally, then O(n) would be a single well-defined object, and one could use transitivity to conclude that 3n=5n. But of course this is false, because O(n) isn't a single function, nor really something that other functions can equal. It's a class of functions, not a function itself.
It would be more appropriate to say that "f(n) belongs to O(n)," or more compactly, "f(n) ∈ O(n)." This is much closer to the real definition, and behaves appropriately when taken literally.
> Misconception 1: “The Equals Sign Means Equality”
The equal sign does mean equals.
> The left-hand-side is a function, the right-hand-side is a … what, exactly? There is no help to be found in the definition. It just says “we write” without concerning itself with the fact that what “we write” is total nonsense.
This is not clear at all !
> If you take it at face value, you can deduce that since 5n and 3n are both equal to O(n), then 3n must be equal to 5n and so 3=5.
Yes well, f(x) = f(y) does not implies x = y. I think people know this ..
... and so on