Question

Let f(n),g(n) and h(n) be functions defined for positive integers such that f(n) = O(g(n)), (g(n)) $\ne$ O(f(n)), g(n) = O(h(n)), and h(n) = O(g(n)). Which one of the following statement is FALSE?

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

Answer 1

The correct option is B f(n) h(n) $\ne$ O(g(n)h(n))

We can verify as:
f $\le$ g BUT g $\nleqq$ f. Therefore f < g
Also g = h as g = O(h) = O(g).
Therefore f < g and g = h
(a) f(n) + g(n) = O(h)(n) + h(n) is true.
$\Rightarrow$ f + g = f + h < h + h
(b) f(n) = O(h)(n) is true.
$\Rightarrow$ f < h
(c) h(n) $\ne$ O(f(n)) is true.
$\Rightarrow$ h $\nleqq$ f is correct.
(d) f(n) h(n) $\ne$ O(g(n)h(n)) is false.
$\Rightarrow$ f .h < g . h implies fh = O(gh)