Help with approaching "advanced" Big-O problems

Question

So an "advanced" problem in my mind may be easy to you but I am just starting to learn this so bare with me.

I want to find the best Big-O of the following problems:

1. $(15n+logn)^3$
2. $n^2logn + n + \sqrt n + logn$

When I look at these problems I find myself in an existential crisis, compared to problems like

Find best Big-O of $100n^2 + n$

Which is straightforward, in my mind.

I guess the part that trips me up is what do I do with the $log$'s and the $\sqrt n$'s?

I am just looking for advice on solving these problems. If you believe that solving for Big-O of the two problems listed will help me understand, then by all means solve them with explanations at each step but I am seeking help with approaching and understand what my first move should be with these problems. Thank you!

Answer 1

$\log(n)$ is smaller than any positive power of $n$. The $\sqrt{n} = n^{1/2}$ is smaller than $n$ but larger than $\log(n).$ If you had $n^{1/4}$ it would be smaller than $n^{1/2}$ or $n$ but larger than $\log(n).$

The second $n^2\log(n) + n+\sqrt{n}+\log(n)$ is probably the easiest to do since the terms are all there for you and you just need to find which one dominates. Of the last three $n,$ $\sqrt{n}$ and $\log(n),$ $n$ is the largest per last paragraph. But is it larger than $n^2\log(n)$? Well, $n^2\log(n)$ is larger than $n^2,$ so it's certainly larger than $n.$

For the first $ (15n+\log(n))^3$ you can multiply it out, and then you have four terms to compare. Or note that the $n$ term dominates the $\log(n)$ term, and infer which of the four terms is going to be the leading order.

Answer 2

One simple fact that will help you most big-O problems we encounter in practice:

$n^\alpha$ is larger (in big-O sense) than $\log n$ for any $\alpha > 0$. $n^{1/2}, n^{1/3}, n^{1/10},$ and so on, are all larger than $\log n$.

spaceisdarkgreen's answer shows how to use this fact.