Redirected
edited by
13,041 views
45 votes
45 votes

Let $f(n)$, $g(n)$ and $h(n)$ be functions defined for positive integers such that 
$f(n) = O(g(n))$, $g(n) \neq O(f(n))$, $g(n) = O(h(n))$, and $h(n) = O(g(n))$.

Which one of the following statements is FALSE?

  1. $f(n) + g(n) = O(h(n) + h(n))$
  2. $f(n) = O(h(n))$
  3. $h(n) \neq O(f(n))$
  4. $f(n)h(n) \neq O(g(n)h(n))$
edited by

7 Answers

Best answer
40 votes
40 votes

Answer is (D).

We can verify as :  $f \leqslant g$  but $g \nleqslant f$. Therefore, $f<g$.

Also, $g=h$, as $g=O(h)$ and $h=O(g)$.

selected by
27 votes
27 votes
LETS ASSUME f(n)= n, g(n)=n^2, h(n)=n^2

option A: n+n^2=O(n^2+n^2)------- TRUE

option B: n+n^2=O(n^2)------------------ TRUE

option C
n=O(n^2)------------- TRUE

option D
n.n^2 != O(n^2 * n^2)= n^3!= O(n^4)----------- FALSE

hence D the answer
20 votes
20 votes
$f(n)=O(h(n))$   (Using transitivity)

$h(n)=Ωf(n)$

$f(n) g(n)=O(g(n) h(n)$ is TRUE.

So, $D$ is FALSE.
edited by
Answer:

Related questions