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?

  • $\begingroup$ It should be not enough to verify that $\lim_{n\to\infty}\frac{n^2+3n^3}{n^3}=3$. $\endgroup$ – agtortorella Jan 25 '12 at 21:12
  • $\begingroup$ Note that technically speaking, your 6th step should be $n \leq 1 + 3n$. $\endgroup$ – Charles Jan 25 '12 at 21:30

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.


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$.

  • $\begingroup$ Additionally, you can remove the dollar sign from the end of your own-line displayed equation. $\;$ $\endgroup$ – user57159 Jan 26 '12 at 6:44
  • $\begingroup$ @RickyDemer Thanks for spotting it, I removed it. $\endgroup$ – Charles Jan 26 '12 at 8:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.