How to pick constants for Big Theta Notation.

200 Views Asked by At

I'm having a problem solving these and understanding big theta notation in general.

i.) Show that if $a(n) = 5n^3 - 97n^2 + 6n - 3$, then $a(n) = \Theta\left(n^3\right)$.

ii.) Suppose that $a(n)$, $b(n)$, $c(n)$, $d(n)$ are positive sequences with $a(n) = \Theta\left(b(n)\right)$ and $c(n) = \Theta\left(d(n)\right)$. Show that if $b(n) \leq d(n)$ holds for all $n$, then $a(n) + c(n) = \Theta\left(d(n)\right)$.

For the first one, I was trying to find the best possible values for $c_1$ and $c_2$ but it always goes out of the rules as $n$ starts growing. For the second I guess I just really don't know where to start from. Any explanation or hint would be helpful really.

1

There are 1 best solutions below

0
On

Hint:

$f(n)\in\Theta\left(g(n)\right)$ if $$0 < \lim_{n\to\infty}\frac{f(n)}{g(n)} <\infty$$

Let $f(n) = 5n^3 - 97n^2 + 6n - 3$, and $g(n) = n^3$. Can you find $\displaystyle\lim_{n\to\infty}\frac{f(n)}{g(n)}$?