0

Logically, I know this affirmation to be true. For all $c$, there is a $n_0>0$ that will make $3n^2 < c n^4$.

But when I try to prove it, I come to the resolution that it's false.

Here is how I get this conclusion:

$$f(n) \leq 3n^2 < n^4.$$

So we have $\forall c$, a $n_0 > n \in \mathbb{N}$ where:

$3n^4 < c n^4$ (This is a step I don't fully grasp, but one that seems to be used a lot in asymptotic notations proof)

Which is false in the case of $c = 1$, $\forall n>0 \in \mathbb{N}$.

What would be another way to go about this?

Gary
  • 31,845
NearFinished_CS
  • 45

1 Answers1

1

Let's rewrite $3n^2 < c \cdot n^4$ as $\frac{3n^2}{n^4}=\frac{3}{n^2}<c$. Left side of last inequality tends to $0$, which fulfills requirements for $n$ and $c$.

As to your last question, then let me ask how you get $n^4$ in left hand of inequality?

zkutch
  • 13,410
  • for the n⁴ in left inequality, it's a part I got wrong. As far as your solution, does this make the use of limits? – NearFinished_CS Jan 29 '22 at 17:05
  • Little-o's definition (https://en.wikipedia.org/wiki/Big_O_notation#Little-o_notation) can be written without mentioning limits, but, essentially, it's equivalent to it. I used, that $\frac{3}{n^2}$ have limit $0$. – zkutch Jan 29 '22 at 17:31