Register

GO Classes 2024 | IIITH Mock Test 5 | Question: 15

• retagged by
326 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
User Avatar

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
User Avatar
Voting & Accepting an answer helps improve the community
Answer:
← PreviousNext →
← Previous in categoryNext in category →

Related questions

303
views
1 answers
1 votes
GO Classes asked Apr 30, 2023
303 views
GO Classes 2024 | IIITH Mock Test 5 | Question: 13
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
User Avatar
343
views
1 answers
2 votes
GO Classes asked Apr 30, 2023
343 views
GO Classes 2024 | IIITH Mock Test 5 | Question: 23
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$.
User Avatar
300
views
1 answers
2 votes
GO Classes asked Apr 30, 2023
300 views
GO Classes 2024 | IIITH Mock Test 5 | Question: 31
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.
User Avatar
254
views
1 answers
1 votes
GO Classes asked Apr 30, 2023
254 views
GO Classes 2024 | IIITH Mock Test 5 | Question: 32
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$
User Avatar
Link Copied!