Site navigation

Assume that f(n) and g(n) are asymptotically positive. Which of the following is correct?

If \(f=o(g)\) and \(g=o(h)\), then \(\frac fg\to 0\) and \(\frac gh\to 0\), so \(\frac fh=\frac fg\cdot\frac gh\to 0\), which means \(f=o(h)\); little-o is transitive. Two…

Choose your answer

Assume that f(n) and g(n) are asymptotically positive. Which of the following is correct?

Select one answer
Answer and explanation

Correct answer C

If f=o(g)f=o(g) and g=o(h)g=o(h), then fg→0\frac fg\to 0 and gh→0\frac gh\to 0, so fh=fg⋅gh→0\frac fh=\frac fg\cdot\frac gh\to 0, which means f=o(h)f=o(h); little-o is transitive. Two big-O bounds combine only to another big-O bound, so they cannot give f=ω(h)f=\omega(h), and two Ω\Omega lower bounds give a lower bound, not an upper bound. Concluding f=Ω(h)f=\Omega(h) from two little-o relations contradicts f=o(h)f=o(h).

Practice for these exams

  • UGC NET Computer Science and Applications

Related question papers

Related exam syllabi

Related questions in this topic