For f(n) = 3n + 2, which notation classifications are correct?

• A. O(n) upper bound only
• B. Omega(n) lower bound only
• C. Theta(n) tight bound only
• D. O(n), Omega(n), and Theta(n)

Answer: (D)

The function grows linearly with n, so constant additive terms don’t change its asymptotic behavior. For an upper bound, 3n+2 is dominated by n up to a constant factor: for example, with c = 4 and n0 = 2, 3n+2 ≤ 4n for all n ≥ 2, so f(n) is O(n). For a lower bound, 3n+2 is at least a constant multiple of n: 3n+2 ≥ 3n for all n, so with k = 3 and n0 = 1, f(n) is Omega(n). Since it has both an upper and a lower bound linear in n, it is Theta(n). The additive constant 2 doesn’t affect the growth rate, which is why all three classifications apply.