Let f$(n)=O(n)$, $g(n)=\Omega(n)$ and $h(n)=\Theta(n)$. Then $g(n)+f(n)\cdot h(n)$ is equal to what among $O(n)$,$\Omega(n)$ and $\Theta(n)$?

Also explain how to evaluate it.

  • $\begingroup$ What did you try? Where did you get stuck? Are you familiar with the definitions of $O$, $\Omega$ and $\Theta$? Does it help you to think informally in terms of numbers in the following way? Very roughly and informally, $f=O(n)$ means that $f\leq n$, $g=\Omega(n)$ means, $f\geq n$ and $h=\Theta(n)$ means that $h$ and $n$ are approximately equal. So, if $g\geq n$ and $h\approx n$, what can you say informally about $g+h$? Then translate that informal intuition back into mathematics. $\endgroup$ – David Richerby Feb 3 '17 at 9:09
  • $\begingroup$ @DavidRicherby Although the informal intuition you describe can help, the question seems to be about adding $f$ and $g$. So the informal question is: knowing $g \geq n$ and $f \leq n$. Can we say something about $f+g$? $\endgroup$ – Discrete lizard Feb 3 '17 at 9:56
  • $\begingroup$ @Discretelizard Actually, now I read it again, it seems to be about $f+g\cdot h$. Doh! I'm going to edit in the LaTeX do we can read it properly! (Do check the edit history to make sure I'm neither cheating nor misreading it again...) $\endgroup$ – David Richerby Feb 3 '17 at 10:14
  • $\begingroup$ @DavidRicherby I know the concepts of these notations as u mentioned, but i am kinda confused in f(n)*h(n) .The answer is $\Omega$(n) but i cant figure out how. And i am particularly interested in the working rule to tackle other queries like these. Thanks $\endgroup$ – Aditya Mohan Feb 3 '17 at 10:58
  • 1
    $\begingroup$ The working rule is to ask yourself how big or small $f+gh$ can be. Think about how you could pick functions $f$, $g$ and $h$ that satisfy the given bounds in a way that makes $f+gh$ as big as possible, and in a way that makes $f+gh$ as small as possible. For example, to make $f+gh$ small, you probably want $f$, $g$ and $h$ to each be as small as they can be. $\endgroup$ – David Richerby Feb 3 '17 at 11:08

Your Answer

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

Browse other questions tagged or ask your own question.