retagged by
352 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

889
views
1 answers
4 votes
GO Classes asked Jan 28
889 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)$
431
views
1 answers
5 votes
GO Classes asked Jan 28
431 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?
829
views
1 answers
11 votes
GO Classes asked Jan 28
829 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.
903
views
1 answers
5 votes
GO Classes asked Jan 28
903 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$