Using Big-O to analyze an algorithm's effectiveness I am in three Computer Science/Math classes that are all dealing with algorithms, Big-O, that jazz. After listening, taking notes, and doing some of my own online searching, I'm pretty damn sure I understand the concept and reason behind Big-O, and what it means when one function is Big-O of the other. The problem I am having right now is when I am asked to PROVE that $f(x) = O(g(x))$. I know the basic order of which kinds of functions are a lower order than others, but its questions that have functions with a lot of combinations of different functions that stump me. I don't know where to start analyzing, and from hearing classmates and professors talk it definitely seems like there's some general rule-of-thumb/algorithm that helps with pretty much every Big-O problem.
Can y'all share some insight into how you go about thinking through these problems?
Give a big-O estimate for this function. For the function $g$ in your estimate $f(x)$ is $O(g(x))$, use a simple function $g$ of smallest order.
$(n^3 + n^2\log n)(\log n + 1) + (17\log n + 19)(n^3 +2)$
Or this one:
Find the least integer $n$ such that $f(x)$ is $O(x^n)$ for each of these functions.
a) $f(x) = 2x^3 + x^2\log x$
b) $f(x) = (x^3 + 5\log x)/(x^4 + 1)$


Give a big-O estimate for this function. For the function $g$ in your estimate $f(x)$ is $O(g(x))$, use a simple function $g$ of smallest order.
  $$x_n=(n^3 + n^2\log n)(\log n + 1) + (17\log n + 19)(n^3 +2)$$

To solve this, one first spots the dominant term in each part, here $n^2\log n\ll n^3$, $1\ll\log n$ and $1\ll n^3$ hence one is left with $$(n^3)(\log n) + (\log n)(n^3),$$ thus, one can guess that $x_n$ is of order $n^3\log n$.
Second one proves that $n^3\log n$ is indeed the smallest order big-O. First this is a big-O: indeed for every $n\geqslant3$, $1\leqslant\log n\leqslant n$ and $1\leqslant n^3$ hence $$x_n\leqslant(n^3 + n^2\cdot n)(\log n + \log n) + (17\log n + 19\log n)(n^3 +2\cdot n^3)=112\cdot n^3\log n.$$
Finally, one proves this is the best big-O: indeed $$x_n\geqslant(n^3 + 0)(\log n + 0) +0=n^3\log n.$$
