Determine Big-O of complex functions

Question

I took an introductory algorithms class this semester and I believe I've gotten the gist of Big-Oh.

However, there are certain functions that I simply cannot manage to make sense of when it comes to deciding their upper bound and most examples online are made on ridiculously easy functions that can be figured out instantly (i.e. $n^6 + n^8 + n^2$ is O($n^8$)). I have an upcoming exam and I'm kind of lost on how to approach such questions, and I'd like a better understanding of how to figure it out.

I would really appreciate an explanation of how to figure whether the following statements are True/False as simply as possible (Please do not give a raw answer "True, False etc", I am truly interested in learning a "methodology" to calculate these as easy as possible):

$$100n^8 + 78n^7 + 30n^6\sqrt{n} + n^2 + n = O(2^n)$$

$$n^4 + 3n^3\log_{2}n - 10n^2 = O(n^3(\log_{2}n)^2)$$

$$\log_{3}n^8 = O(\log_{8}n)$$

$$\log_{5}n^3 = O(\log_{3}n)$$

$$\log_{3}n^n = O(n^{\log_{2}n})$$

$$\sqrt{n} = O(n/(\log_{2}n))$$

$$2^n = O(100n^8)$$

$$2^{n \log_{2}n} = O(n^{\log_{2}n})$$

Answer 1

We'll just go by the definition.$f(x)=O(g(x))$ if there exists a positive real number M and a real number $x_0$ such that $|f(x)|\leq Mg(x) {\text{ for all }}x\geq x_{0}$

We can easily see that if $$\lim_{n\to\infty} \frac{|f(x)|}{g(x)} < \infty$$ we can find such M and $x_0$. So this is all you need to check! Conversely, if limit is unbounded, $f \neq O(g)$.

As an example, take $-n^8$ and $k^n$ for some k>1. The limit $n^8/k^n$ always goes to zero.

Hence, $n^8 = O(k^n)$ $ \forall k>1$

You can solve all of your questions similarly(and instantly) :)

Answer 2

I would like to add some hints to cybershiptrooper's answer.

$\log$ grows very slowly, particularly $\log(n) = O(n)$ (prove this!), but not the other way, not even $n = O(\log(n)^k)$ for an arbitrarily large $k$ (prove this!). So your second example is wrong.

The base of $\log$ does not matter for the asymptotic behaviour. Can you prove that $\log_k(n) = c \cdot \log_l(n)$ with a constant $c$ (which depends on $k$ and $l$?
Hence you can replace $\log_k(n)$ by $O(\ln(n))$. (Attention: Be careful if the argument of $\log$ is, say, an exponential function ...)

Exponential functions are growing really fast, particularly $p(n) = O(e^n)$ for any poloynomial $p$, but not the other way. So your second-to-last example is wrong.