Multiplying and adding different asymptotioc notations

Question

does anyone knows how to perform such calculations Example:

O(n^2) + THETA(n) + OMEGA(n^3) = ?

or

O(n^2) * THETA(n) * OMEGA(n^3) = ?

In general, how to add and multiply different asymptotic notations?

Answer 1

O gives an upper bound;

Ω gives a lower bound;

Θ gives an asymptotic bound;

Wikipedia has a nice chart to explain these.

Therefore these really aren't comparable in general.

For your first case,

O(n^2) + Θ(n) + Ω(n^3)

Let's first tackle O. The first term tells us O(n^2), and the second term tells us O(n). Based on just these two, we know so far we have O(n^2) for an upper bound. However, the third term tells us nothing whatsoever about an upper bound! So we really cannot conclude anything about O.

The point here is that O and Θ gives you information about O only, and Ω and Θ gives you information about Ω only. This is because Θ(g(n)) implies both O(g(n)) and Ω(g(n)), so we can change Θ into whichever of O and Ω is appropriate for the given analysis.

However, the three together, or even just O and Ω, leaves you clueless since neither O nor Ω implies anything about the other.

Answer 2

You can't. Suppose you know that a > 0 and b < 10. Then you have no information about a+b. It could be anything.

Big-O and Big-Omega act similarly for functions.

Answer 3

While my above answer is correct for general functions and bounds, in computer science we typically consider only positive functions. Thus in your first example, we have:

O(n^2) + Theta(n) + Omega(n^3) = Omega(1)+Theta(n)+Omega(n^3) = Omega(n^3)

This stems from the assumption that the functions are all positive. That is, all functions are Omega(1).