# Let $f(n)=\Omega(n), g(n)=O(n)$ and $h(n)=\theta(n)$ then $f(n).g(n)+h(n)$ is?

Let $$f(n)=\Omega(n), g(n)=O(n)$$ and $$h(n)=\theta(n)$$ then $$f(n).g(n)+h(n)$$ is?

My attempt:

Lets $$f(n)=g(n)=n$$, then $$f(n).g(n)+h(n)=\Omega(n^2)+\theta(n)=\Omega(n^2)$$

But given answer is $$O(n)$$. Now sure where I have have committed mistake or if I am missing something. How it can be $$O(n)$$?

• What is the bracket notation, $[f(n).g(n)] + h(n)$? Generally, $f(n) g(n)+h(n)$ is clearer. Just in case, does the original problem look like $\lfloor f(n)g(n)\rfloor+h(n)$ or $\lceil f(n)g(n)\rceil+h(n)$? – John L. Dec 10 '18 at 12:47
• @Apass.Jack Need to improve awareness. :) – Mr. Sigma. Dec 10 '18 at 13:03

You have a fault in $$f(n).g(n) = \Omega(n^2)$$. Because, $$g(n) = O(n)$$ and you can't say $$g(n)$$ is $$n$$ or $$\frac{1}{n^2}$$ for example. Hence, we can't say nothing about $$f(n).g(n)$$. For more example: $$g(n) = \frac{1}{n}, f(n) = n \Rightarrow f(n).g(n) = \Theta(1)$$ $$g(n) = 1, f(n) = n \Rightarrow f(n).g(n) = \Theta(n)$$ $$g(n) = \frac{1}{n^2}, f(n) = n \Rightarrow f(n).g(n) = o(1) (\text{little-o})$$ $$g(n) = n, f(n) = n \Rightarrow f(n).g(n) = \Theta(n^2)$$
As we don't know about $$f(n).g(n)$$. However, we can say $$f(n).g(n) + h(n) = \Omega(n)$$ as $$h(n) = \Theta(n)$$ and $$f(n).g(n) \geq 0$$.
• Thanks, its helpful. But given answer is $O(n)$. – Mr. Sigma. Dec 10 '18 at 10:08
• @Mr.Sigma. The final answer cannot be true! Because we have some counterexample as you see. A counterexample is $f(n) = n, g(n) = n, h(n) = n$, hence $f(n).g(n) + h(n) = \Theta(n^2)$ and it is not in $O(n)$. – OmG Dec 10 '18 at 10:11
• I don't think the asker is claiming that $f(n)g(n)=\Omega(n^2)$ for all functions $f=\Omega(n)$ and $g=O(n)$. Rather, they're just saying that $f(n)=g(n)=n$ gives a counterexample to the "official" answer of $O(n)$. – David Richerby Dec 10 '18 at 10:34
• @DavidRicherby Yes, I was giving counterexample. But now I think its $\Omega(n)$ precisely as the answer explained. Right? – Mr. Sigma. Dec 10 '18 at 12:03
• @Mr.Sigma. $\Omega(n)$ seems to be correct, yes. – David Richerby Dec 10 '18 at 12:22