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?

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

2 Answers 2


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

  • $\begingroup$ So is 7 not the correct answer then? And how do we prove that logx = o(x)? $\endgroup$ Nov 20 at 19:00
  • $\begingroup$ 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. $\endgroup$ Nov 20 at 19:11
  • $\begingroup$ 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)? $\endgroup$ Nov 20 at 19:16
  • $\begingroup$ Yep, that does it $\endgroup$ 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)|<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$.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .