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?
Answer and explanation
Correct answer C
If and , then and , so , which means ; little-o is transitive. Two big-O bounds combine only to another big-O bound, so they cannot give , and two lower bounds give a lower bound, not an upper bound. Concluding from two little-o relations contradicts .
Practice for these exams
-
UGC NET Computer Science and Applications