First time here? Checkout the FAQ!
+2 votes

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 (9.1k points) 4 65 210 | 60 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 (4k points) 6 12 28
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
asked in Algorithms by Akriti sood Veteran (14.8k points) 15 153 318 | 60 views
+1 vote
0 answers
asked in Computer Networks by sh!va Veteran (30.2k points) 108 374 697 | 122 views
+2 votes
1 answer
asked in Revision by Arjun Veteran (319k points) 583 1458 2974 | 139 views

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
Top Users Oct 2017
  1. Arjun

    23684 Points

  2. Bikram

    17288 Points

  3. Habibkhan

    9194 Points

  4. srestha

    6486 Points

  5. Debashish Deka

    5478 Points

  6. jothee

    5178 Points

  7. Sachin Mittal 1

    4910 Points

  8. joshi_nitish

    4504 Points

  9. sushmita

    4080 Points

  10. Rishi yadav

    3998 Points

Recent Badges

Nice Question Tesla!
Nice Question Ashwani Kumar 2
Nice Comment Pooja Palod
Famous Question Harsh181996
Verified Human ASK
Good Comment Bikram
Good Comment Arjun
Nice Comment Arjun
Famous Question Meenakshi Sharma
Famous Question Meenakshi Sharma
27,426 questions
35,275 answers
33,523 users