How does adding big O notations works
can someone please explain how adding big O works.
i.e. $O(n^3)+O(n) = O(n^3)$
why does the answer turn out this way? is it because $O(n^3)$ dominates the whole expression thus the answer is still $ O(n^3)$
$\endgroup$3 Answers
$\begingroup$Big $O$ notation is the upper bound notation, so given two functions, such that $f\in O(g)$ ($f$ is upper bounded by $g$ to the linear constant from some point) the sum $O(f) + O(g) = O(g)$, and as $n \in O(n^3)$ (meaning $n$ too is bounded in the limit by some multiple of $n^3$) we have also that $O(n)+O(n^3)=O(n^3)$. It can be seen as a "domination" that you refer in the question.
$\endgroup$ $\begingroup$The formal definition for equalities which contain $\;O(\cdot)\;$ and related notations, is that these notations are sets, and that such an equality holds if it holds for every function in each left hand side set, and for some function in each right hand side set.
(Anyone: Feel free to insert a reference; I don't have one at hand.)
Therefore $$ O(n^3)+O(n) = O(n^3) $$ is formally an abbreviation for $$ \langle \forall f,g : f \in O(n^3) \land g \in O(n) : \langle \exists h : h \in O(n^3) : \langle \forall n :: f(n) + g(n) = h(n) \rangle \rangle \rangle $$ (I won't go into the proof of this statement here; the first answer should help you there.)
Note how this general definition applies to the special case of $$ f(n) = O(g(n)) $$ where it gives us $$ \langle \exists h : h \in O(g(n)) : \langle \forall n :: f(n) = h(n) \rangle \rangle $$ which can quicky be simplified to the usual $$ f \in O(g(n)) $$
$\endgroup$ $\begingroup$Equality $O(n^3)+O(n)=O(n^3)$ we can understand as equality between sets - they are two forms of recording the one and same set. Formally, left side is subset of right side and reverse:
$O(n^3)+O(n) \subset O(n^3)$ and $O(n^3) \subset O(n^3)+O(n) $.
If "dominance" is understood as inequality $n \leqslant n^3$, then we can say that, yes, $n^3$ "dominates" $n$.
$\endgroup$
