Let F be an algorithm with complexity function f(n),and let G be an algorithm with complexity function g(n).If there exists a positive constant K such that the ratio f(n)/g(n)is less or equal to K for all n greater or equal to 1,then
A) the two algorithms are asymptotically equivalent
B) the algorithm F is asymptotically no worse than G
C) the algorithm F is asymptotically no better than G
D) Nothing intelligent can be said about the relative performance of the two algorithms.

Question

Quizplus · Accepted Answer

The given condition implies that f(n) is bounded by K times g(n) for all n greater or equal to 1. This means that the worst-case running time of F is no more than K times the worst-case running time of G. Hence, F is asymptotically no worse than G.

Let F Be an Algorithm with Complexity Function F(n),and Let