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)$?

  • $\begingroup$ 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)$? $\endgroup$ – John L. Dec 10 '18 at 12:47
  • $\begingroup$ @Apass.Jack Need to improve awareness. :) $\endgroup$ – 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$.

  • $\begingroup$ Thanks, its helpful. But given answer is $O(n)$. $\endgroup$ – Mr. Sigma. Dec 10 '18 at 10:08
  • 1
    $\begingroup$ @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)$. $\endgroup$ – OmG Dec 10 '18 at 10:11
  • 1
    $\begingroup$ 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)$. $\endgroup$ – David Richerby Dec 10 '18 at 10:34
  • $\begingroup$ @DavidRicherby Yes, I was giving counterexample. But now I think its $\Omega(n)$ precisely as the answer explained. Right? $\endgroup$ – Mr. Sigma. Dec 10 '18 at 12:03
  • $\begingroup$ @Mr.Sigma. $\Omega(n)$ seems to be correct, yes. $\endgroup$ – David Richerby Dec 10 '18 at 12:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.