Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.
Sign up to join this community
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?
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)$.
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$.
