If not BigO, then BigOmega?

Question

So, if the function or runtime is not BigO of f (n), can we say it BigOmega of f (n)?

Answer 1

No. For example, the function

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

is neither in O(n)nor in Ω(n): for any values Nand cthere will always be a value n > Nsuch that f(n) > c*n(therefore it cannot be in O(n)) and another value m > Nsuch that f(m) < c*m(therefore it cannot be in Ω(n)).

Answer 2

No, not necessarily.

, . g, 1/n n n*n.

BigO f (n) = n ( ). , n * n .

BigOmega f (n) = n, , g (n) >= k * f (n).

Answer 3

, .. n < m → f (n)\leq f (m), , f (n)\neq O (g (n) f (n) =\Omega (g (n)).

, , f (n) = g (n) ^ 2 n g (n-1) n , g (n) = f (n) ^ 2 n f (n -1) n , f (0) = 2, g (0) = 2.

Both are monotonously growing, but not big - about the others (they grow very fast).