Big O or Big Omega?

Question

Here's my answers to Is A O or Ω of B ? Do you think I got it right?

A               B           O   Ω
(log n)^3       N           No  Yes
2n^2+4n         4n^2        Yes No
n!              2^n         No  Yes
n^5             n^4         No  Yes
100             10000       Yes No
n^2             (1.5)^n     No  Yes

Answer 1

Big O is asymptotically upper bound while Big Omega is asymptotically lower bound.

• A = O(B) if and only if limit A(n)/B(n) < C as n approach infinity and C is a positive constant.
• A = Ω(B) if and only if limit A(n)/B(n) > C > 0 as n approach infinity and C is a positive constant.

You can use Wolframe Alpha to find such limit.

A               B           O   Ω
(log n)^3       N           Yes  No
2n^2+4n         4n^2        Yes Yes
n!              2^n         No  Yes
n^5             n^4         No  Yes
100             10000       Yes Yes
n^2             (1.5)^n     Yes  No

For example:

• limit n²/1.5ⁿ as n goes to infinite is 0. Therefore, we know that 1.5ⁿ grow faster than n^2 as n is getting larger and larger. So, 1.5ⁿ is upper of n² but not a lower bound of n².
• limit (2n^2+4n)/(4n^2) as n goes to infinite is 0.5.
  • We could say that limit A(n)/B(n) < 1. Therefore, A = O(B).
  • We could say that limit A(n)/B(n) > 0.4 > 0. Therefore, A = Ω(B).