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

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.

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.