如果不是BigO,那么BigOmega？

Question

因此,如果函数或运行时间不是f(n)的BigO,我们可以说它的BigOmega是f(n)吗？

Answer 1

不.例如功能

        / n^n if 2|n
 f(n) = |
        \ 0   otherwise

既不O(n)也不在?(n):对于任何值N和c总是会有一个值n > N,使得f(n) > c*n(所以它不能在O(n))和另一个值m > N,使得f(m) < c*m(所以它不能在?(n)).