Multiplication and addition of various asymptotic notation

Question

Does anyone know 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 various asymptotic notation?

Answer 1

O gives the upper bound ;

Ω gives a lower bound ;

Θ gives an asymptotic estimate ;

Wikipedia has a nice schedule to explain this.

Therefore, they are really not comparable at all.

For your first occasion

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

Let O first be taken. The first member tells us O(n^2) , and the second member tells us O(n) . Based only on these two, we know that we have O(n^2) for the upper bound. However, the third term says nothing about the upper bound! Therefore, we cannot do anything about O

The fact is that O and Θ provides information only about O , and Ω and Θ provides information only about Ω . This is due to the fact that Θ(g(n)) implies both O(g(n)) and Ω(g(n)) , so we can change Θ depending on whether O and Ω suitable for a given analysis.

However, the three together, or even just O and Ω , leave you wordless, since neither O nor Ω implies anything else.

Answer 2

You can not. 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

Although my answer above is correct for common functions and boundaries, in computer science we usually only consider positive functions. So 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 is due to the assumption that all functions are positive. That is, all the functions of Omega(1) .