0

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

Julia
  • 496

3 Answers3

1

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.

Clement C.
  • 67,323
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)$

Hippalectryon
  • 7,730
  • Thank you! Rookie question, but how do I know $\mathcal{O}(log_{2}(x^9+5))$ = $\mathcal{O}(log_{2}(x^9))$ without writing it out from the definition? – Julia Jul 01 '15 at 09:13
  • Excuse me I fixed my comment. – Julia Jul 01 '15 at 09:15
  • 1
    @Julia $x^9+5=\mathcal{O}(x^9)$ thus $\log_2(x^9+5)=\mathcal{O}(\log_2(x^9))$ – Hippalectryon Jul 01 '15 at 09:18
  • 2
    @Julia: another way to see it is that for any constant $c>0$$\log(x+c) = \log x + \log(1+c/x)$. The first term goes to infinity, the second to $0$. – Clement C. Jul 01 '15 at 09:19
0

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)$.
Bernard
  • 175,478