（O与的一些变形）某些作者用一种与我们稍微不同的方式来定义；_

（O与 $\Omega$ 的一些变形）某些作者用一种与我们稍微不同的方式来定义 $\Omega$ ；假设我们使用

（读作“ $\Omega$ 无穷”）来表示这种可选的定义。若存在正常量c，使得对无穷多个整数n，有 $f(n)\geq cg(n)\geq 0$ ，则称f(n)=

(g(n))。

a.证明：对渐近非负的任意两个函数f(n)和g(n)，或者

或者f(n)=

(g(n))或者二者均成立，然而，如果用 $\Omega$ 来代替

，那么该命题并不为真。

b.描述用

代替 $\Omega$ 来刻画程序运行时间的潜在优点与缺点。

某些作者也用一种稍微不同的方式来定义O，假设用O'来表示这种可选的定义。我们称f(n)=O'(g(n))当且仅当 $\left| f(n) \right|=O(g(n))$ 。

c.如果使用O'代替O但仍然使用 $\Omega$ ，下面定理中“当且仅当”的每个方向将出现什么情况？有些作者定义 $\tilde{O}$ （读作“软O”）来意指忽略对数因子的O：

$\tilde{O}$ (g(n))={f(n)：存在正常量c,k和n₀，使得对所有 $n\geq n_{0}$ ，有 $0\leq f(n)\leq cg(n)lg^{k}(n)$ }

d.用一种类似的方式定义 $\tilde{\Omega}和\tilde{\Theta}$ 。证明与下面定理相对应的类似结论。

定理：对任意两个函数f(n)和g(n)，我们有f(n)= $\Theta(g(n))$ ，当且仅当f(n)=O(g(n))且f(n)= $\Omega(g(n))$

（O与的一些变形）某些作者用一种与我们稍微不同的方式来定义；