Some authors define ? in a slightly different way than we do; let?s use ?^?(read ?omega infinity?) for this alternative definition. We say that f (n) = ?^? (g(n)) 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 O? (read ?soft-oh?) to mean O with logarithmic factors ignored:

O?(g(n)) = {f (n) : there exist positive constants c, k, and n₀ such that 0 ? f (n) ? cg(n) lg^k(n) for all n ? n₀}.

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

Theorem 3.1

Transcribed Image Text:

f (n) lim = 0 g(n) n→00