GATE CSE
First time here? Checkout the FAQ!
x
+2 votes
59 views

Which of the following two is correct?

  • If f(n) = Ο(g(n)) then h(f(n)) = Ο(h(g(n)))
  • If f(n) ≠ Ο(g(n)) then g(n) = Ο(f(n))
asked in Algorithms by Boss (8.8k points)   | 59 views
second only.

1 Answer

+2 votes
Best answer
Both of them are incorrect.

For first one, let's assume $f(n) = n$ and $g(n) = n^2$. Clearly, $f(n) = O(g(n))$. Now consider $h(n) = 1/n$.

$h(f(n)) = 1/f(n) = 1/n$ and $h(g(n)) = 1/g(n) = 1/n^2$. Now for no constants $c$ and $n_0$, $0 \leq h(f(n)) \leq ch(g(n))$ for all $n > n_0$. (You can confirm this by plotting both $1/n$ and $1/n^2$).

So first statement is incorrect.

For second statement.

CLRS says "Not all functions are asymptotically comparable." That is, for two functions $f(n)$ and $g(n)$, it may be the case
that neither $f(n) = O(g(n))$ nor $f(n) = \Omega(g(n))$ holds. An example would be $f(n) = n$ and $g(n) = n^{1+\sin{n}}$

Hence, both of the statements are incorrect.
answered by Loyal (3.4k points)  
edited by

please explain Not all functions are asymptotically comparable. bit more.

That statement means that it is possible for two functions $f(n)$ and $g(n)$ to exist such that, you can't apply the definitions of any of $O$, or, $\Omega$, or, $\Theta$, or, $o$, or, $\omega$ between them.

Considering the same $f(n) = n$ and $g(n) = n ^ {1 + \sin{n}}$, Since $1 + \sin{n}$ oscillates between 0 and 2, $g(n)$ oscillates between $n^0$ and $n^2$, hence it's not possible to find two constants, $c$ and $n_0$ such that $0 \leq f(n) \leq cg(n)$ for all $n > n_0$ or similarly for other definitions.

You can get more insights from here

Related questions

0 votes
1 answer
1
asked in Algorithms by Akriti sood Veteran (13.4k points)   | 54 views
+1 vote
0 answers
2
+2 votes
1 answer
3


Top Users Sep 2017
  1. Habibkhan

    7838 Points

  2. Warrior

    2812 Points

  3. Arjun

    2696 Points

  4. rishu_darkshadow

    2692 Points

  5. A_i_$_h

    2456 Points

  6. manu00x

    2040 Points

  7. nikunj

    1980 Points

  8. Bikram

    1864 Points

  9. makhdoom ghaya

    1790 Points

  10. SiddharthMahapatra

    1718 Points


26,243 questions
33,815 answers
80,261 comments
31,168 users