GATE IT 2004 | Question: 55

Question

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?

• A. $f(n) + g(n) = O(h(n) + h(n))$
• B. $f(n) = O(h(n))$
• C. $h(n) \neq O(f(n))$
• D. $f(n)h(n) \neq O(g(n)h(n))$

Comments

@Avir Singh Take f(n) = log n , g(n) = n , h(n) = n. And then solve the question.

---

In option A     f(n)+g(n)=O(h(n)+h(n))

f(n)+g(n)=O(2(h(n)))
f(n)+g(n)=O(h(n))
f(n)+g(n) <= h(n)

Now since h(n)= Θ(g(n))

f(n)+h(n) <= h(n)
It is false as LHS is greater than RHS.

How this procedure is wrong???

---

Here we are checking the order so the greater order will be the overall order in LHS

n^2 +n^3 = O(n^3)

as on LHS n^3 is greater only this will be evaluated and the smaller terms would be ignored in comparison so

n^3 = O(n^3) which is correct

similarily f(n)+g(n) = O(h(n))

                g(n) = O(h(n))                  which is correct

Answer 1

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

Comments

but why is option D is false

suppose f(n) = n, g(n) = n^2 , h(n) = n^2,

then f(n)h(n) = n*n^2 = n^3

O(g(n)h(n)) = O(n^2 * n^2 ) = O(n^4)

so is not n^3 = O(n^3) ?

---

Option D says  f(n)h(n)≠O(g(n)h(n)).

What you are telling is f(n)h(n)=O(g(n)h(n)) which is true.

Hence option D is  false.

---

o means O also so B is correct

Answer 2

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

Comments

You're actually saying that in option d: LHS != RHS thus making the statement TRUE, which is not the case.

---

sir can u check option c one more tim e

Answer 3

$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.

Comments

option A:

f(n)+g(n)=O(g(n)+h(n)  [ g(n) = O(h(n)), and h(n) = O(g(n)) which proves g(n)=h(n) ]

             =g(n)+h(n)

             =O(h(n))+h(n)

---

here it is asked to tell false.

So, option D false.rt?

---

yep...!!option D is false and so is the Answer !

Answer 4

I think option a is mis printed And option d is false