HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Is Ω(f+g) = Ω(min(f,g))?

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
minstackoverflowprogramming

Problem

We know that $O(f(n)+g(n))=O(max(f(n),g(n)))$.

So can we say that $\Omega(f(n)+g(n)) = \Omega(min(f(n),g(n))$?

Then what is $\Theta(f(n)+g(n))$ equal to?

Solution

Assuming $f,g > 0$, we have
$$\max(f(x),g(x)) 0$, it is also true that $\Omega(f(x)+g(x)) = \Omega(\min(f(x),g(x)))$, in the sense that if $h(x) \in \Omega(f(x)+g(x))$ then also $h(x) \in \Omega(\min(f(x),g(x))$. The stronger bound $\Omega(f(x)+g(x)) = \Omega(\max(f(x),g(x)))$ also holds.

I have mentioned two interpretations of equality. In fact the second one (which really corresponds to $\subseteq$ in this case) is actually the standard one – equality is not symmetric! However, in the case of big $\Theta$ both notions fortunately coincide.

Context

StackExchange Computer Science Q#50893, answer score: 9

Revisions (0)

No revisions yet.