Variations on O and ΩSome authors define Ω, in a slightly different way than we do; let’s...

Variations on O and Ω

Some authors define Ω, in a slightly different way than we do; let’s use (read “omega infinity”) for this alternative definition. We say that if there exists a positive constant c such that f(n) ≥ cg(n) > 0 for infinitely many integers n.

a. Show that for any two functions f(n) and g(n) that are asymptotically nonnegative, either f(n) = O(g(n)) or f(n) = (g(n)) or both, whereas this is not true if we use Ω in place of .

b. Describe the potential advantages and disadvantages of using  instead of Ω to characterize the running times of programs.

Some authors also define O in a slightly different manner; let’s use O′ for the alternative definition. We say that f(n) = O′(g(n)) “if and only if” |f(n)| = O(g(n)).

c. What happens to each direction of the “if and only if” in Theorem 3.1 if we substitute O for O′ but still use Ω?

Some authors define Õ (read “soft-oh”) to mean O with logarithmic factors ignored:

Õ(g(n)) = {f(n): there exist positive constants c, k, and n0 such that

    0 ≤ f(n) ≤ cg(n) 1 gk(n) for all n ≥n0}.

d. Define  in a similar manner. Prove the corresponding analog to Theorem 3.1.