Question about Big O Notation

Question

I don't seem to understand big-O notation very well. If someone would explain it to me as well as explain how this problem would work

Let f(n) = (3$^n$$^+$$^1$ - 3)/2. For each of the following universal statements, is it true or false? (No need for proof).

Since, there's no need for a fullout proof, what's a good way to figure it out? (or you can just teach me the proof)

i. f(n) is O(2$^n$)

ii. f(n) is O(4$^n$)

iii. f(n) is O(n$^n$)

iv. f(n) is O(n!)

v. f(n) is O(n$^3$)

vi. f(n) is O(log n)

All of them don't have to be answered. I just want to know how to solve the problem. Honestly, I really have no idea how to solve this problem. I need this answered somewhat urgently. Thank you!

Answer 1

A quick way to check if $f$ is big Oh of $g$ is by computing the ratio of its limits. In other words,

If the limit$$\lim_{n \to \infty} \left | \frac{f(n)}{g(n)} \right | $$ exists and is finite, then you can say that $f \in O(g)$. Formally this would mean there is an $N \in \mathbb{N}$ such that $\forall n \geq N \implies |f(n)| < \epsilon|g(x)|$

For your function, you can actually just ignore the constants and consider $f(n) = 3^{n}$ since the rest of the terms are $O(3^n)$.

i) Without even doing the limit, you know that $3^{n}$ can never be "smaller" than $2^n$. So this is false.

ii) Yes this is possible and in fact true.

iii) Yes it is true (when $n$ is large).

iv) Yes it is true.

v) No this is false. In the long run, polynomials can never surpass exponential.

vi) Similar reasoning as (v)