2
$\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$
1
  • $\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
    Commented May 17, 2014 at 5:38

1 Answer 1

3
$\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$
6
  • $\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$ Commented May 17, 2014 at 5:52
  • $\begingroup$ Check this link (much better) scs.ryerson.ca/~mth110/Handouts/PD/bigO.pdf $\endgroup$
    – IAmNoOne
    Commented May 17, 2014 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$ Commented May 17, 2014 at 6:02
  • $\begingroup$ @user151524, I think you forgot to post your next question! $\endgroup$
    – IAmNoOne
    Commented May 17, 2014 at 6:05
  • $\begingroup$ Yeah i pressed Enter instead of Shift+enter haha $\endgroup$ Commented May 17, 2014 at 6:06

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .