Difficulty proving a function exists in both Big $O$and Big $\Omega$

Question

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?

Answer 1

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.

Answer 2

Following the Family of Bachmann–Landau notations, the formula you used is actually used to show that $f(n)$ is in $\Omega(g(n))$.

To answer your question, if you want to prove that $f(n) \in \Theta(n^3)$, then you need to find two constants $k_1$ and $k_2$ such that when $n \to \infty$, you have

$$ k_1 \cdot n^3 \leq n^2 + 3n^3 \leq k_2 \cdot n^3 $$

I believe that in this case, if you take $k_1 = 3$ and $k_2 = 4$, you can prove directly the inequality.

EDIT: Note that although the decomposition of the inequality you gave is correct, you don't need to be that much detailed. For instance, to prove that $n^3 \leq n^2 + 3n^3$, you can just say that it's equivalent to $0 \leq n^2 + 3n^3 - n^3$, which is trivial when $n \to \infty$.

Similarly, to prove that $n^2 + 3n^3 \leq 4n^3$, you can just observe that $n^2 \leq n^3$, and it follows that $n^2 + 3n^3 \leq n^3 + 3n^3$.