0

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.

rtpax
  • 296

3 Answers3

0

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))$.”

amd
  • 53,693
0

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})$$

Kamil Jarosz
  • 4,984
0

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.

Harald Hanche-Olsen
  • 31,960