retagged by
348 views
4 votes
4 votes

Given that $f(n)=O(g(n))$ (where $\mathrm{O}$ is Big-O) and $f(n)=\Omega(g(n))$, which of the following statement is always true?

  1. $f(n)=o(g(n))$ (here $o$ is small-$o).$
  2. $f(n)=\theta(g(n))$.
  3. $f(n)=\omega(g(n))$.
  4. Both A and B are always true.
retagged by

1 Answer

1 votes
1 votes

given $f(n)=O(g(n))$ and $f(n)=\Omega(g(n))$ $\rightarrow$ $f(n)=\theta(g(n))$

consider $f(n)=n$ and $g(n)=2n$

$f(n)=O(g(n))$ and $f(n)=\Omega(g(n))$

$f(n)=\theta(g(n))$

$f(n)\not=\omega(g(n))$

$f(n)\not=o(g(n))$

$f(n)\not=o(g(n))$, by definition for this to be true $f(n)$ should be less for all values of c in $cg(n)$ which is not the case in the above example

$f(n)\not=\omega(g(n))$, by definition for this to be true $f(n)$ should be greater for all of c in $cg(n)$ values which is not the case in the above example

Answer:

Related questions

886
views
1 answers
4 votes
GO Classes asked Jan 28
886 views
Professor Fiorina uses the following algorithm to merge $k$ sorted lists, each containing $n / k$ elements.She takes the first list and merges it with the second list using a ... $\theta(k \log n)$
430
views
1 answers
5 votes
GO Classes asked Jan 28
430 views
Consider the following weighted graph, where the weight of every edge is written on the edge itself.What is the number of possible minimum spanning trees for the above graph?
823
views
1 answers
11 votes
GO Classes asked Jan 28
823 views
Consider the following statements related to Huffman's algorithm:$\text{S1:}$ If there is exactly one symbol with a frequency of $1 / 3$, and all other symbols have frequencies ... , but $\mathrm{S} 2$ is true.S1 is false, and S2 is false.
900
views
1 answers
5 votes
GO Classes asked Jan 28
900 views
A total of $n$ points are equally spaced around a circle and are labelled with the integers $1$ to $n$, in order. Two points are called diametrically opposite if the ... $ and $35$ are diametrically opposite, then $n$ equals$54$55$56$57$