patternMinor
Is Ω(f+g) = Ω(min(f,g))?
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?
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.
$$\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.