Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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 $\Theta$ to prove that $f(n)$ is in both $O(n{^3})$ and $\Theta(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?

share|improve this question
    
It should be not enough to verify that $\lim_{n\to\infty}\frac{n^2+3n^3}{n^3}=3$. –  Giuseppe Tortorella Jan 25 '12 at 21:12
    
Note that technically speaking, your 6th step should be $n \leq 1 + 3n$. –  Charles Morisset Jan 25 '12 at 21:30

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

share|improve this answer
    
Additionally, you can remove the dollar sign from the end of your own-line displayed equation. $\;$ –  Ricky Demer Jan 26 '12 at 6:44
    
@RickyDemer Thanks for spotting it, I removed it. –  Charles Morisset Jan 26 '12 at 8:47

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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