1
$\begingroup$

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!

$\endgroup$
  • $\begingroup$ Technically it should ask for "big oh at $n =...$", but I guess we may assume it is in the long run as $n \to \infty$ $\endgroup$ – IAmNoOne May 17 '14 at 5:38
2
$\begingroup$

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)

$\endgroup$
  • $\begingroup$ Thank you so much for the quick answer! How would you do an actual proof? it's not required for this question, but if you don't mind showing me a few examples. I still don't really understand it too well $\endgroup$ – xNinjaKittyx May 17 '14 at 5:52
  • $\begingroup$ Check this link (much better) scs.ryerson.ca/~mth110/Handouts/PD/bigO.pdf $\endgroup$ – IAmNoOne May 17 '14 at 5:55
  • $\begingroup$ So lets see if I understand this. For my next problem, it says $$Let f(n) = 3^n/7$$ It is safe to assume 3$^n$? i. f(n) is O(n) - false ii. f(n) is O(n$^2$) - false iii. f(n) is O(n$^3$) - false iv. f(n) is O(n$^n$) - true $\endgroup$ – xNinjaKittyx May 17 '14 at 6:02
  • $\begingroup$ @user151524, I think you forgot to post your next question! $\endgroup$ – IAmNoOne May 17 '14 at 6:05
  • $\begingroup$ Yeah i pressed Enter instead of Shift+enter haha $\endgroup$ – xNinjaKittyx May 17 '14 at 6:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.