Site navigation

If f(n)=θ(g(n)) and g(n)=O(h(n)), then which of the following is true?

From \(f = \Theta(g)\) there is a constant c with \(f(n) \le c\,g(n)\) for large n, and from \(g = O(h)\) a constant d with \(g(n) \le d\,h(n)\). Chaining them gives \(f(n)…

Choose your answer

If f(n)=θ(g(n)) and g(n)=O(h(n)), then which of the following is true?

Select one answer
Answer and explanation

Correct answer A

From f=Θ(g)f = \Theta(g) there is a constant c with f(n)≤c g(n)f(n) \le c\,g(n) for large n, and from g=O(h)g = O(h) a constant d with g(n)≤d h(n)g(n) \le d\,h(n). Chaining them gives f(n)≤cd h(n)f(n) \le cd\,h(n), so f(n)=O(h(n))f(n) = O(h(n)). A tight bound does not follow, because h may grow much faster: with f=g=nf = g = n and h=n2h = n^2, f is O(h)O(h) but not Θ(h)\Theta(h), and h is not O(f)O(f).

Practice for these exams

  • UGC NET Computer Science and Applications

Related question papers

Related exam syllabi

Related questions in this topic