retagged by
332 views
3 votes
3 votes

Let $n$ be a positive integer.
Consider the two statements below:

  • $\text{S1:}$ If $f(n)>g(n)$ for all $n$ then $g(n)$ is ALWAYS o( $f(n))$. where $o$ is small-oh.
  • $\text{S2:}$ If $f(n)<g(n)$ for all $n$ then $f(n)$ is ALWAYS $o(\mathrm{~g}(n))$. where $o$ is small-oh.

Which of the following is the correct option?

  1. $\text{S1}$ is correct but $\mathrm{S} 2$ is incorrect
  2. $\text{S1}$ is incorrect but $\mathrm{S} 2$ is correct
  3. Both are correct
  4. Both are incorrect
retagged by

1 Answer

6 votes
6 votes
Answer-D

Please note that $f(n)>g(n)$ or $f(n)<g(n)$ are usual comparisons and not asymptotic comparisons.
Formally, we can not use $> \text{ or } <$ signs for asymptotic comparisons. We do it informally for sake of understanding. This question is exactly pointing out the same thing.
 
Question says  $f(n)>g(n) \color{magenta}\text{ for all }$ $n$. It only means the absolute comparison of function values and has nothing to do with asymptotic comparisons as of now.

Let $f(n)=2 n+1$ and $g(n)=n$, it satisfies $f(n)>g(n)$ for all $n$.

But It doesn't mean $g(n)=o(f(n))$
edited by
Answer:

Related questions

307
views
1 answers
1 votes
GO Classes asked Apr 30, 2023
307 views
Let $\text{G = (V, E)}$ be a connected, undirected graph with edge weights $w: \text{E} \rightarrow \mathbb{Z}$. Suppose $\text{G}$ has a ... no cycles$\text{G}$ contains at most one cycleAll edge weights are differentNone of the above
350
views
1 answers
2 votes
GO Classes asked Apr 30, 2023
350 views
Which of the following is/are TRUE?In the worst case, merge sort runs in $O\left(n^2\right)$ time.Depth-first search of a graph is asymptotically faster than ... a binary search tree leaves the same tree as inserting $y$ and then $x$.
307
views
1 answers
2 votes
GO Classes asked Apr 30, 2023
307 views
Suppose we have a set of $n$ values. There are always at least one negative value and at least one positive value in the set.What is the worst case time ... known) and arranged in descending order then it takes $\theta(n)$ in worst case.
259
views
1 answers
1 votes
GO Classes asked Apr 30, 2023
259 views
Let $\text{G = (V, E)}$ be a simple undirected graph, and $s$ be a particular vertex in it called the source. For $x \in \text{V},$ let $d(x)$ denote the shortest distance in ... $(u, v)$, we have $d[v]=d[u]+1$