CODEWITHSUNDEEP
algorithmtheoryasymptotic-complexity
Sławosz
Sławosz

Reputation: 11687

Multiplying and adding different asymptotioc notations

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?

Upvotes: 4

Views: 2322

Answers (3)

tskuzzy
tskuzzy

Reputation: 36446

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).

Upvotes: 1

tskuzzy
tskuzzy

Reputation: 36446

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.

Upvotes: 4

PengOne
PengOne

Reputation: 48398

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.

Upvotes: 5

Related Questions