Big-Oh notation question

117 Views Asked by At

When we have a question like so:

What is the smallest integer $n$, such that $f(x) = x^{5.7}(\log x)^{1.2}$ is $O(x^n)$?

Would we go about the question as so: round up $x^{5.7}$ to become $x^6$. Since $\log x < x$, we can treat the $\log x$ as $x$, and $\rightarrow x^6x = x^7$, so the smallest integer $n: 7$

Is this correct?

3

There are 3 best solutions below

4
On

That $\log x < x$ is insufficient—after all, we also have $x/2 < x$, but $x/2$ is, by construction, $\Theta(x)$. You need the fact that $\log x = o(x)$.

0
On

For positive $a,b$ let set $f(x)=\dfrac{\ln(x)^a}{x^b}$ it is not to difficult to see that $f\searrow$ at infinity.

Indeed $f'(x)=\dfrac{\overbrace{\ln(x)^{a-1}}^{>0}(\overbrace{a-b\ln(x)}^{<0})}{\underbrace{x^{b+1}}_{>0}}<0\quad$ for $x$ large enough.

In particular since $f$ is continuous and $f(x)>0$ for $x>1$ we can conclude that $f$ is bounded (it is decreasing so cannot go to positive infinity, has a lower bound zero so cannot go to negative infinity, hence bounded). $$\exists M>0\text{ : }|f(x)|<M\quad\forall x>1$$

Now we just plug $x=u^2$ and use the logarithm multiplicative to additive property to show that the denominator is negligible.

$$f(x)=f(u^2)=\dfrac{2^a\ln(u)^a}{u^bu^b}=\dfrac{2^af(u)}{u^b}\le \dfrac {2^aM}{u^b}\to 0\quad\text{when }u\to\infty$$

As a consequence $\ln(x)^a=o(x^b)$ for any positive $a,b$

Since the logarithm at any power is negligible as long as $x$ is sufficiently large, we can simply bound $$\ln(x)^{1.2}=o(x^{0.1})=O(x^{0.1})$$

Therefore $x^{5.6}\ln(x)^{1.2}=x^{5.6}O(x^{0.1})=O(x^{5.7})=O(x^6)$

And $6$ is the minimal integer that is greater than $5.7$.

0
On

Assume $t \ge 720$. Then $$ {\rm e}^t = \sum\limits_{n = 0}^\infty {\frac{{t^n }}{{n!}}} \ge \frac{{t^6 }}{{720}} \ge t^5 \Longrightarrow t \ge \log (t^5 ). $$ Suppose that $x \ge 720^5$, and take $t = x^{1/5}$ in the above inequality to get $$ x^{1/5} \ge \log x \Longrightarrow x^{0.24} \ge \log ^{1.2} x. $$ Therefore, $$ x^{5.7} \log ^{1.2} x \le x^{5.94} \le x^6 $$ provided $x \ge 720^5$.