edited by
611 views
0 votes
0 votes

Let $f\left ( n \right )$m  $g\left ( n \right )$ and $h\left ( n \right )$ be functions whose domain is a subset of positive integers such that $f\left ( n \right )= O\left (n^{2}\right), g\left ( n \right )= O\left(n^{3}\right), h\left ( n \right )= O\left(n^{4}\right).$ Then:

  1. $f \left ( n \right ) +g \left ( n \right )= O \left(n^{3}\right)$   
  2. $h \left ( n \right ) -g \left ( n \right )=O \left ( n \right )$    
  3. $f \left ( n \right ).g \left ( n \right )=O\left( n^{4}\right)$   
  4. $h \left ( n \right ) .g \left ( n \right ) =O\left(n^{7}\right)$

Which of the above is/are incorrect?

  1. $(d)$ $only$
  2. $(c)$ $only$
  3. $(b)$ $and$ $(d)$ $only$
  4. $(b)$ $and$ $(c)$ $only$
edited by

1 Answer

Best answer
2 votes
2 votes
Here  (a) is correct because f(n) = O(n^2) and g(n) = O(n^3), and f(n) + g(n) = O(n^3) (Addition Rule asymptotic behavior)
Similarly item (d) is also correct according to the Multiplication Rule for asymptotic behavior. Hence the answer is (D).
selected by
Answer:

Related questions

0 votes
0 votes
1 answer
3
Bikram asked Jan 16, 2017
322 views
How many times $fibon$$\left ( 3 \right )$ is called during invocation of $fibon$ $\left ( 6 \right )$?$fibon(x) = fibon(x-1) + fibon(x-2)$$fibon(0) = 1$$fibon(1) = 1$345...