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
    It should be not enough to verify that $\lim_{n\to\infty}\frac{n^2+3n^3}{n^3}=3$.2012-01-25
  • 0
    Note that technically speaking, your 6th step should be $n \leq 1 + 3n$.2012-01-25

2 Answers 2