Is this proof for big-Oh of $(x+2)log(x^9 + 5)$ correct?

Question

Is my proof that $(x+2)log_{2}(x^9+5)$ is $\mathcal{O}(xlog_{2}x)$ correct when x tends towards infinity?

$\left | f(x) \right | = \left | (x+2)log_{2}(x^9 + 5) \right |$

$\leq \left |(x+2)log_{2}(x^{10}) \right |$ for $x \geq 2$ <---- This is the step that I am unsure of.

$ = 10(x+2)log_{2}x$

$ \leq 10(x+2x)log_{2}x $ for $x \geq 2$

$ = 30x log_{2}x$

Since $\left | f(x) \right | \leq 30xlog_{2}x$, $f(x)$ is $\mathcal{O}(xlog_{2}x)$

Answer 1

I didn't take a specific look at the intervals you took for your inequalities, but the general method you used works, though you are over complicating things.

You just need to write $x+2=\mathcal{O}(x),\log_2(x^9+5)=\mathcal{O}(\log_2(x^9))=\mathcal{O}(\log_2(x))$ hence $(x+2)log_{2}(x^9+5)=\mathcal{O}(xlog_{2}x)$

Answer 2

Your proof looks correct (for the step you are unsure of, you basically use $x^9(x-1) \geq 5$ which clearly holds for $x\geq 2$, and the fact that $\log_2$ is increasing).

In the big-Oh notation, whether you write specify the base 2 for the logarithm (writing $\log_2$) is irrelevant -- they are all the same, up to constants.

Answer 3

Maybe using general rules of asymptotic analysis is simpler:

• $x^9+5=O(x^9)$ since $5=o(x^9)$, hence $\log_2(x^9+5)=O(\log_2 x^9)=O(9\log_2 x) =O(\log_2 x)$
• $x+2=O(x)$
• So $\;(x+2)\log_2(x^9+5)=O(x)O(\log_2 x)=O(x\log_2 x)$.