我如何证明n ^ 3.5不是O(n ^ 3)

我如何证明n ^ 3.5不是O(n ^ 3)？

我正在为我的算法类做这个.

它说我需要使用Contradiction证明来证明它!

让我们使用大O 的定义.

f(n)= O(g(n))表示存在常数C和值n ₀,使得对于每个n> n ₀,| f(n)| <= C | g(n)|.

我们想通过矛盾证明f(n)= n ^3.5和g(n)= n ³.因此,假设存在这样的常数C | n ^3.5 | <= C | n ³ | 成立.当然,这是错误的,这就是为什么:例如,取n = C ¹⁰,并看到| C ³⁵ | <= C | C ³⁰ |,与C ³⁵ <= C ^31相同.对于任何C> 1来说,这显然是错误的.对于任何更大的n(回想我们需要n> n ₀),这显然也不成立.