Prove or disprove $n^3/O(n) = O(n^2)$

Question

Intuitive it feels like it should be proven, but I'm stuck on trying to prove, and I can't think of a way to disprove it either.

To prove it, I need to show that (for one side): $n^3/O(n) = cn^2$ for all $n>n_0$ and exist $n_0>0$ and $c>0$. $\{ t(n)| exist: c>0, exist: n_0>0 ,for-all: n>n_0 \}$
so I wrote this $$n^3/t(n) >n^3/cn = n^2/c $$
now I don't know how to continue from here

score 1 · Accepted Answer · answered Apr 18 '20 at 10:07

1

It doesn't work. Take $R(n)=\sqrt n\in \mathcal O(n)$. Then $$\frac{n^3}{R(n)}=\sqrt n n^2\notin \mathcal O(n^2).$$

answered Apr 18 '20 at 10:07

Surb

55,662

1

Or simply $R(n)=1$. – lhf Apr 18 '20 at 10:49

Prove or disprove $n^3/O(n) = O(n^2)$

1 Answers1