# Big-Oh notation question

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?

• You've shown $7$ works, but you haven't shown it is minimal. Clearly $5$ doesn't work. What about $6$? Nov 20 at 19:07
• For this problem, it would be useful to consider the order of $x log(x)$ relative to the orders of $x$ and $x^2$. Nov 20 at 19:10
• I don't see how 6 could work, since we can't simply ignore the log term, correct? Nov 20 at 19:19

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

• So is 7 not the correct answer then? And how do we prove that logx = o(x)? Nov 20 at 19:00
• I made no comment about what the correct answer is. To figure out how one might show that $\log x = o(x)$, refer to the definition of little-oh. Nov 20 at 19:11
• By definition of little-oh, we need to show that the ratio log(x)/x approaches zero as x goes to infinity. Doing calc, we see that limit when x approaches infinity log(x)/x results in zero. Is this enough to prove that log(x) is o(x)? Nov 20 at 19:16
• Yep, that does it Nov 20 at 20:34

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