Page 41, Exercise 2

Show that the following statements are incorrect:
(a) 10n² + 9 = O(n). For every positive c, the LHS (left hand side) is greater than cn whenever n is greater than c/10. So, there are no positive constants c and n₀ that satisify the definition of big O.
(b) n² log n = θ(n²). There is no positive c₂ for which the LHS is less than or equal to c₂n² for n greater than or equal to 2.
(c) n² / log n = θ(n² ). If this statement were correct, there would be a positive c₁ and n₀ such that the LHS is greater than or equal to c₁n² for all n greater than or equal to n₀. But, this inequality does not hold for n greater than 2^1/c₁.
(d) n³ 2ⁿ + 6n² 3ⁿ = O(n² 2ⁿ). It is easy to see that positive c and n₀ do not exist such that the LHS is less than or equal to cn²2ⁿ for every n greater than or equal to n₀ (actually, this is true even if we ignore the first term on the LHS).
(e) 3nⁿ = O(2ⁿ ). Once again, one can show that positive c and n₀ such that the LHS is less than or equal to c2ⁿ for every n greater than n₀ do not exist.