0
$\begingroup$

I recently learned about big-O notation and I think I get it but in some uses it does not line up with what I think I understand it as. In the wikipedia page it calls using the form $f(x) = O(g(x))$ an abuse of notation because all it is saying is that there is a relationship between the two. It goes on to use similar notation to say

$g(x) = h(x) + O(f(x))$

expresses the same as

$g(x) - h(x) = O(f(x))$

This is easy enough to understand, but I fail to take valuable meaning from statements such as

$(n+O(n^{1/2}))(n + O(\log n))^2 = n^3 + O(n^{5/2})$

where it would be impossible to set it up as an equality with my big-O statement on one side then "take away" the misleading notation. If someone could help me understand this I would greatly appreciate it.

$\endgroup$
0
$\begingroup$

In equalities, such as $$(n+O(n^{1/2}))(n+O(\log n))^2=n^3+O(n^{5/2})$$

The "$O(f(x))$" means "some function that is $O(f(x))$" i.e.

$$(n+f_1(n))(n+f_2(n))^2=n^3+f_3(n)$$ Where $$f_1(n)\in O(n^{1/2}),\quad f_2(n)\in O(\log n),\quad f_3(n)\in O(n^{5/2})$$

$\endgroup$
0
$\begingroup$

Think of an expression like $g(x) = h(x) + O(f(x))$ as shorthand for “$g(x) = h(x) + \phi(x)$, where $\phi(x)\in O(f(x))$.”

$\endgroup$
0
$\begingroup$

Basically, equations with big-Oh notation on both sides need to be read left to right. For example, $$(n+O(n^{1/2}))(n + O(\log n))^2 = n^3 + O(n^{5/2})$$ means that for any functions $f$ and $g$ so that $f(n)=n+O(n^{1/2})$ and $g(n)=(n+O(\log n))^2$, it is true that $f(n)g(n)=n^3+O(n^{5/2})$. (Never mind that this statement, though true, is almost ridiculously weak. A better right hand side would be $n^2+O(n^{3/2})$.)

It is unfortunate that this notation breaks the symmetry of the equality relation. What this indicates is not that equality is not symmetric, but rather that the equality symbol is being abused in these calculations. But this usage has gotten so entrenched it is difficult to change it at present.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.