Asymptotic notation Big $\mathcal{O}$ How to understand absolute value in an expression

Question

$|2\mathcal{O}(f(n))-\mathcal{O}(f(n))+d|=\mathcal{O}(f(n)). d>0 $ constant and $f(n)>1$.

I know how to prove such claims ,but when an absolute value appears I do not understand how to relate to it, I tried to divide it into two cases but It was hard and now I'm not sure that It can be proven.

how i can understand that? Is it possible to prove it at all?

Answer 1

The equation \begin{align*} |2\mathcal{O}(f(n))-\mathcal{O}(f(n))+d|=\mathcal{O}(f(n))\tag{1} \end{align*} means that $S_1\subseteq S_2$,

• where $S_1$ is the set of all functions of the form \begin{align*} |2 g_1(n)-g_2(n)+d| \end{align*} such that there exists constants $C_1,C_2>0$ with \begin{align*} &|g_1(n)|<C_1 |f(n)|\qquad\qquad \forall n\in\mathbb{N}\\ &|g_2(n)|<C_2|f(n)|\qquad\qquad \forall n\in\mathbb{N} \end{align*}

• and where $S_2$ is the set of all functions $$g_3(n)$$ such that there is a constant $C_3>0$ with \begin{align*} |g_3(n)|<C_3|f(n)|\qquad\qquad \forall n\in\mathbb{N} \end{align*}

We obtain from the inequalities above \begin{align*} \color{blue}{|2 g_1(n)-g_2(n)+d|}&\leq2|g_1(n)|+|g_2(n)|+d\\ &\color{blue}{<} 2C_1 f(n)+C_2 f(n)+d f(n)\tag{2}\\ &=\color{blue}{\left(2C_1+C_2+d\right) f(n)}\tag{3} \end{align*}

In (2) we also use the assumption $f(n)>1$ to get $d< d f(n)$.

Conclusion: From (3) we conclude with $C_3=2C_1+C_2+d$ that whenever a function is in $S_1$ it is also in $S_2$ and the claim (1) follows.

Hint: Note that we are dealing in (1) with one way equalities. The right side of the equation does not give more information than the left side, and it may give less. The right side is a crudification of the right side.

A thorough introduction and also a reasoning for the $=$ - notation (namely tradition (three times) and the natural approach) is presented in chapter Asymptotics in Concrete Mathematics by R.L. Graham, D.E. Knuth and O. Patashnik.