Can someone help me understand how to work with $\log(x)$ is $O(x)$?

508 Views Asked by At

Just recently learned how to prove if a function is Big O of another, for example proving $f(x) = 10$ is $O(x)$, $f(x) = 3x + 7$ is $O(x)$, $f(x) = 17x + 11$ is $O(x^2)$ or $f(x) = x^2 + 100$ is $O(x^2)$ and what not. Proving if some $f(x)$ is not $O(g(x))$ is no issue either. But when it comes to doing something like that with $\log$s, I'm at a complete loss. Like prove if $f(x) = x\log x$ is $O(x^2)$ or $f(x) = 5\log x$ is $O(x)$. I have no idea where to even begin and the textbook I'm using is not much help, so any chance someone could walk me through this step by step would be great. A couple examples would be awesome too, I learn best with examples. Any help would be appreciated.

1

There are 1 best solutions below

4
On

One of the common sufficient conditions for $f(x) = O(g(x))$ is $$\lim_{x \to \infty} \frac{f(x)}{g(x)} < \infty.$$

In your case, $$ \lim_{x \to \infty} \frac{x \ln x}{x^2} = \lim_{x \to \infty} \frac{\ln x}{x} = 0 < \infty. $$