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 a homework problem, we've been asked to prove the following:

$$6n^2+20n \in O(n^3)$$

$$6n^2+20n \not \in \Omega(n^3)$$

Since BigO is defined as $g(n) \leq c \cdot f(n)$ for a function $f(n)$, set of functions $g(n)$, some real constant $c$ and non-negative integer $N$ such that for all $n\geq N$, I worked the first part to

$$6n^2+20n \leq c \cdot n^3$$ $$\frac{6n^2+20n}{n^3} \leq \frac{cn^3}{n^3}$$ $$\frac{6n+20}{n^2} \leq c , n \geq 1$$

Therefore, for $c=26$ and $N=1$, this function satisfies the requirements of Big O.

My issue is that Big $\Omega$ is an identical formula, with the exception of flipped inequality. In order to prove the second part, I need show that no possible $c$ will work.

However, for $n=0, c=0$,

$$\frac{6(0)+20}{0^3} \geq 0 \Rightarrow 0\geq 0$$ which is true.

I also did some more thinking and came up with this series:

$$\frac{6n^2+20n}{c} \geq \frac{c \cdot n^3}{c}$$ $$\frac{6n^2+20n}{c} \geq n^3$$

However, plugging in $n=1$ results in $\frac{26}{c}\geq 1$, meaning this inequality holds true for all $c > 26$

How can I show that no possible $c$ value will work for the second equation?

share|improve this question
add comment

1 Answer 1

According to the definition I know, $6n^2+20n\in\Omega(n^3)$ means that there exists a positive number $c$ such that $6n^2+20n\ge c n^3$ for almost all $n$.

Apart from your problematic dividing by $0$, you seem to look for a different $c$ for each $n$. That is not the correct thing to do. Let $c>0$ be given. For which $n$ does $6n^2+20n\ge cn^3$ hold? Divide both sides by $n^2$ to obtain $6+\frac{20}n\ge cn$. Now the left hand side is $\le 26$ for all $n\ge 1$, whereas the right hand side becomes arbitrarily large and thus is $>26$ for almost all $n$ (for which $n$ exactly, depends on $c$, though). Hence for no positive $c$ the required inequality holds for almost all $n$.

share|improve this answer
add comment

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.