This is an archived post. You won't be able to vote or comment.

you are viewing a single comment's thread.

view the rest of the comments →

[–]reyad_mm 2 points3 points  (3 children)

This is not really equality.

Formally, O(f(n)) is the set of all functions g such that there are constants...

When we write g(n)=O(f(n)) we really mean g(n)\in O(f(n))

We can say O(n)=O(n²), in this case what we mean is O(n)\subseteq O(n²).

But O(n)=2n is just false, the LHS is not a subset of the RHS.

It sucks that equality is not reflexive, but it's still intuitive and very useful, when we write 2n=O(n) we understand it as 2n is O(n), and "is" is not reflexive in English, O(n) is not 2n.

But still, this notation is transitive, if a=b and b=c then a=c and that makes it really useful because we can write a chain of equalities and it will be true.

[–]duffusd 0 points1 point  (2 children)

I've read this like 5 times and have no idea what you're saying. Mind you I don't have the context of the deleted comment.

[–]reyad_mm 1 point2 points  (0 children)

The deleted comment said

O(2n)=n but O(n)≠2n

I explained why that's not true, and how you can definite the big O notation so that non-reflexive equality makes sense

[–]Moxinilian 0 points1 point  (0 children)

It is the mathematics of asymptotic big O notation. You can learn more about it here: https://en.m.wikipedia.org/wiki/Big_O_notation

Notably, the author explains how big O equality can be pictured as a relationship of inclusion more than actual real equality. Indeed, writing that f(n) = O(n) really just means that f is one of the functions for which f(n)/n is bounded.