Evaluate the following expression: O(2n) + Ω(2n) + Θ(2n) = ?

Answer: Ω(2^n)

Explanation: Let f(n) be a function in O(2^n), g(n) be a function in Ω(2^n), and h(n) be a function in Θ(2^n).

Because h(n) ∈ Θ(2^n), there exist constants c>0 and n0 such that for all n ≥ n0, h(n) ≥ c·2^n. Therefore f(n)+g(n)+h(n) ≥ h(n) ≥ c·2^n for large n, so the sum is Ω(2^n).

We cannot conclude O(2^n) or Θ(2^n), because the Ω(2^n) term may be asymptotically larger than 2^n.

Counterexample:

• Take f(n)=2^n (which is O(2^n)), h(n)=2^n (which is Θ(2^n)), and g(n)=2^{2n} (which is Ω(2^n)).

• Then f(n)+g(n)+h(n)=2^n+2^{2n}+2^n ≈ 2^{2n}, which is not O(2^n) and so not Θ(2^n).

• This shows only the lower bound Ω(2^n) is guaranteed.

Conclusion: The expression evaluates to Ω(2^n).