retagged by
307 views

1 Answer

Best answer
3 votes
3 votes
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.
edited by

Related questions

2 votes
2 votes
0 answers
2
2 votes
2 votes
1 answer
3
Arjun asked Jan 11, 2016
460 views
How do you compare associativity (in cache) to chaining in hash table?
1 votes
1 votes
1 answer
4
radha gogia asked Oct 19, 2015
330 views
when the limit register contains the maximum physical address of the process so then how can we compare directly the logical address with the limit register contents ?