f(n) = 3n² + 5n + 8 is in
AO(n) but not O(n²)
BO(log n) and O(n²)
CO(n²) and Θ(n²)
DO(2^n) only
Answer & Solution
Correct answer: C. O(n²) and Θ(n²)
For large n, the dominant term is 3n². Drop the constant 3 and lower-order terms (5n, 8) to get O(n²). Since f is bounded both above and below by constant multiples of n², it is also Θ(n²). It is NOT O(n) because n² grows faster than any constant times n.
Related questions
An NP-hard problem differs from an NP-complete one because NP-hard problemsThe first problem proved to be NP-complete wasA problem X is NP-complete if and only ifWhy does theoretical computer science draw the line at 'polynomial-time' for tractability?Which set inclusion is established (i.e., proven, not open)?The class NP is the set of decision problems for whichFloyd-Warshall detects the presence of a negative cycle byTopological sort is well-defined for