1

I have trouble starting this homework assignment for my discrete math class. Does $\Theta(n^3+2n+1) = \Theta(n^3)$ hold? Justify your answer.

We need to prove $n^3+2n+1 \in \Theta(n^3)$ AND $n^3 \in \Theta(n^3+2n+1)$\

First lets solve $n^3+2n+1 \in \Theta(n^3)$

This is where I'm getting stuck. I'm supposed to do something with transitivity but I don't entirely know how to do that. Do I use the definitions like:

$l|n^3| \leq n^3+2n+1 \leq k|n^3|$ let $l = 1$ and $k=1$

and so on?

Any tips would be helpful.

Dart Feld
  • 47
  • Let $k=4$ and $3n^3\geq 2n+1$ for all $n\geq n_0$ for some $n_0$ (which you can find, probably $n_0=1$. – kingW3 Feb 21 '18 at 23:46

1 Answers1

1

Note that by definition $$ f\in O(g)\text{ as }x\rightarrow a $$ whenever $$ \limsup_{x\rightarrow a}\left|\frac{f(x)}{g(x)}\right|<\infty $$ in this case since

$$\dfrac{n^3+2n+1}{n^3}\to1$$

we have that $n^3+2n+1∈O(n^3)$ and $n^3∈O(n^3+2n+1)$.

user
  • 154,566