CODEWITHSUNDEEP
big-ocomputer-science
odaiwa
odaiwa

Reputation: 335

Does O(f(n)) + Ω(g(n)) equal Ω(f(n)) + O(g(n))?

Is the following equation true? :

O(f(n)) + Ω(g(n)) = Ω(f(n)) + O(g(n))

I know that Big O means no better than (function), and Big Omega means no worse than (function). But I don't know if that makes the above statement true or false.

Upvotes: 0

Views: 256

Answers (2)

OmG
OmG

Reputation: 18838

We have three general cases (for increasing functions):

  • Case 1: f(n) ∈ o(g(n)) (note the "little-oh").

    In this case, O(f(n)) ⊂ O(g(n)) and Ω(g(n)) ⊂ Ω(f(n)). Hence, O(f(n)) + Ω(g(n)) is a proper subset of O(g(n)) + Ω(f(n)).

    For example, if f(n) = n and g(n) = n3, then n2 is in Ω(f(n)) + O(g(n)), but it is not in O(f(n)) + Ω(g(n)).

  • Case 2: f(n) ∈ Θ(g(n))

    In this case, O(f(n)) = O(g(n)) and Ω(g(n)) = Ω(g(n)), so the two sets are equal.

  • Case 3: f(n) ∈ ω(g(n))

    This case is equivalent to case 1, just with f and g flipped. So by symmetry, we have that O(f(n)) + Ω(g(n)) is a proper superset of O(g(n)) + Ω(f(n)).

In sum, these two sets are not equal in general.

Upvotes: 1

RiaD
RiaD

Reputation: 47620

Let $f(n) = n, g(n)= 2^n$

$t(n) = 2n$ is in second set, because $n = Ω(f(n))$ and $n = O(g(n))$, but not in the first

Upvotes: 0

Related Questions