4
$\begingroup$

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?

  • 0
    Note that technically speaking, your 6th step should be $n \leq 1 + 3n$.2012-01-25

2 Answers 2

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

  • 0
    @RickyDemer Thanks for spotting it, I removed it.2012-01-26
2

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.