证明/反驳BigO和BigTheta

Question

我有充分理解如何证明以下某些陈述的问题.

例如,我有一个声明:n^2logn = O(n^2).纠正我,如果我错了,但这个规定,n^2是bigO的n^2logn.意味着n^2增长得快于n^2logn.现在我们将如何证明这一点？我假设我需要使用感应证明,我试图使用但是在这个过程中卡住了.我可以重写这句话n^2logn <= n^2吗？

是否有可能使用归纳法反驳某些东西？例如,反驳n!=O(n^n).或者通过简单地表明任意值(例如大于2)不满足该陈述来反驳该陈述是否有效？

最后为了清楚起见,bigTheta声明方程式在增长正确时是等价的？

Answer 1

索赔n^2logn是O(n^2)手段直观使得n ^ 2logn增长最多快n^2-asymptotically(这种说法是错误的).

根据定义,这意味着存在一些常数c,N,使得每个常数n>N:c*n^2logn <= n^2

反驳它是非常简单的.
假设(错误地)声明是真的,让我们N,c成为常数:

c*n^2logn <= n^2
c*logn <= 1
logn <= 1/c

但是c是不变的,并且有一些n>N这样的logn > 1/c- 矛盾.

你可以通过展示别的东西来反驳,例如 - 如果你通过归纳表明n! < n^n- 你实际上反驳了这个说法n! = n^n

关于大the,我试图在Big Theta Notation中详细解释这个问题- 大Theta究竟代表什么？