closed by
353 views
1 votes
1 votes
closed with the note: Duplicate of : https://gateoverflow.in/3698/gate2004-it-55..If u have doubt regarding the question, plz comment there itself..
Let f(n), g(n) & h(n) be 3 non-negative functions defined as follows:

$f(n) = O(g(n))\; \; \; g(n) \neq O(f(n))$

$g(n) = O(h(n))\; \; \; h(n) = O(g(n))$

Which of the following is false?

(A). f(n) + g(n) = O(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))$
closed by

1 Answer

1 votes
1 votes

f(n) =O(g(n)) but g(n) != O(f(n))


it means g(n) is strictly greater than f(n) both can't be equal, and it is f(n) = o(g(n))  // not tightest upper bound

g(n) = O(h(n)) and h(n) = O(g(n)), hence f(n) = Θ(g(n))

Suppose f(n) = n  $ g(n) = n^{2} $  $  h(n)=n{^2}$
(A) is true
(B) is true
(C) is true
(D) is False  as $n^{3} = O(n^{4})$
 

edited

Related questions

0 votes
0 votes
1 answer
1
Chaitanya Kale asked Nov 10, 2022
294 views
Can we write f(2$^{n/a}$) = Θ(2$^{n}$) for any integer a >0?