If f(n) = O(g(n)) and g(n) = O(f(n)), what else must be true?
I f(n) = Ω(g(n))
II g(n) = Ω(f(n))
III f(n) = θ(g(n))
A) I
B) II
C) I and II
D) I, II, and III

Name: If f(n) = O(g(n)) and g(n) = O(f(n)), what else must be true? I f(n) = Ω(g(n)) II g(n) = Ω(f(n)) III f(n) = θ(g(n)) A) I B) II C) I and II D) I, II, and III
Brand: Quizplus
Rating: 4.9 (41 reviews)

Question

Quizplus · Accepted Answer

If f(n) = O(g(n)) and g(n) = O(f(n)), then f(n) and g(n) are asymptotically tight, meaning f(n) = θ(g(n)). This implies both f(n) = Ω(g(n)) and g(n) = Ω(f(n)).

If F(n) = O(g(n)) and G(n) = O(f(n)), What Else