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?
Answer and explanation
Correct answer A
From there is a constant c with for large n, and from a constant d with . Chaining them gives , so . A tight bound does not follow, because h may grow much faster: with and , f is but not , and h is not .
Practice for these exams
-
UGC NET Computer Science and Applications