f(n) is in O(g(n)) means there exist constants c > 0 and n_0 ≥ 0 such that for all n ≥ n_0,
Af(n) = c · g(n) exactly
Bf(n) ≤ c · g(n)
Cf(n) ≥ c · g(n)
Df(n) > c · g(n)
Answer & Solution
Correct answer: B. f(n) ≤ c · g(n)
Big-O is an upper bound: f(n) ≤ c · g(n) for some positive constant c and all sufficiently large n. Equality is Theta (tight); the ≥ inequality is Omega (lower bound); strict > is not how the bound is defined.
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