Asymptotic notation big(O) and Big(Omega)

Question

f(n) = 6*2^n + n^2

big(O) = 2^n

big(Omega) = 2^n

In above equation both big(O) and big(Omega) has same value. If big (O) is upper bound and big(omega) is lower bound shouldn't big(omega) = n^2. Why the both have same value?

Answer 1

It's true that O and Ω are upper and lower bounds, respectively, but they are more similar to ≤ and ≥ than to < and >. Just like it's possible that, simultaneously a ≥ b and a ≤ b (without contradiction), so can a function be both O and Ω of a different function (in fact, that's one of the ways to define Θ).

Here, for large enough n,

• 6 2ⁿ + n² ≤ 12 2ⁿ so 6 2ⁿ + n² grows at most (up to a multiplicative constant)like 2ⁿ does (it is O of it).

• Conversely, 6 2ⁿ + n² ≥ 0.1 2ⁿ so 6 2ⁿ + n² grows at least (up to a multiplicative constant) like 2ⁿ does (it is Ω of it).

Note that you don't have to use the same multiplicative constants. The conclusion is that 6 2ⁿ + n² = Θ( 2ⁿ)