Sometimes in the literature a definition of Ω that is symmetric with the definition of o is used; we call this the stronger definition of Ω:
A function fin) is Ω.(g(n» if there exists real numbers a,b>O such that for all integers n ≥ a, (n) ≥ b*g(n).
Clearly, if a function fin) is Ω(g(n)) under the stronger definition, then it also is under the standard definition. Although the reverse is not true, for virtually all algorithms addressed in this book, if the running time is Ω.((n)) under the standard definition, then it is also under the stronger definition. The standard definition can capture situations such as when infinitely often the algorithm takes only O(1) time to indicate that the input is illegal for some reason but on the other hand infinitely often uses (n) time. The stronger definition has nice mathematical symmetry with the definition of O and, as we will observe in this problem, simple mathematical identities work out more cleanly with the stronger definition.
Let (n) and g(n) be any non-negative functions and let F(n) and G(n) denote functions that are Ω((n» and Ω.(g(n)) respectively.
A. Using the stronger definition of Ω, prove that for n>O the following identities are always true:
B. Using the standard definition of Q, give examples that make the identities of Part A false.