For an algorithm analysis homework assignment, I've been asked to show that
$$f(n) = n{^2} + 3n{^3} \in \Theta(n{^3})$$
This means that its necessary to use the definitions of $O$ and $\Omega$ to prove that $f(n)$ is in both $O(n{^3})$ and $\Omega(n{^3})$.
The formula for determining a $O$ set result is
$$g(n) \leq c f(n)$$
where c is a positive real constant and $g(n)$ is the set of valid complexity functions for which $c$ is valid.
In my case, I've assigned $g(n) = n{^3}$ and $c= 1$, thus beginning my work as
$$f(n) = n^2+3n^3$$
$$g(n) = n^3$$
$$n^3 \leq (n^2 + 3n^3) \cdot c$$
$$n^3 \leq (n^2 + 3n^3)(1)$$
$$\frac{n^3}{n^2} \leq \frac{n^2+3n^3}{n^2}$$
$$n \leq 3n$$
$$n \geq \frac{1}{3}n$$
I belive I've followed the rules, but this doesn't seem right. Am I on the right track or did I make an error somewhere?
Best Answer
This kind of problem typically is easier to attack by writing out the definitions. You want to find constants $N$, $c_1$ and $c_2$, such that for all natural numbers $n > N$, you have $$ c_1 n^3 \le f(n) \le c_2 n^3 $$ As you seem to have noticed, the left inequality is easy: take $N = 1$ and $c_1 = 1$, since for $n\in \mathbb{N}$ you have $n^3 \le 3n^3\le 3n^3 + n^2$. This is half of what you needed. For the upper bound, here is a trick that can be turned into a more general result: figure out when the lower order term becomes less than the higher order one. Here is it easy. For $n\in \mathbb{N}$, you have $$ n^2 \le n^3 $$ Just plug this in: $$ f(n) = 3n^3 + n^2 \le 3n^3 + n^3 = 4n^3 $$ so take $c_2 = 4$.
Now, as a comment suggested, there is another approach when the limit exists. Observe that: $$ f(n) / n \to 3 $$ as a sequence. Now if you unravel the definitions, this means that for all $\epsilon > 0$, there is an $N$ such that $n > N$ implies that $3 - \epsilon\le f(n)/n^3\le 3 + \epsilon$. Take $\epsilon = 1$ and multiply through by $n^3$ to get the result.