The running time of an algorithm is O(g(n)) if and only if:

(A) its worst-case running time is O(g(n)) and its best-case running time is Ω(g(n)).

(B) its worst-case running time is Ω(g(n)) and its best-case running time is O(g(n)).

(C) O(g(n))=Ω(g(n)) (O= big O).

(D) o(g(n))∩ω(g(n)) is non-empty. (o= small o)

Choose the correct answer from the options given below:

(A) (A) only (B) (B) only

1. Aonly
2. B(B) only
3. C(C) only
4. D(D) only

Pick an option to check yourself, or open the answer below.

Show answer & explanation

Correct answer: A. only

Explanation

The official key takes statement (A) as the defining condition. Statements (C) and (D) are false: O(g) and Ω(g) are different classes, and o(g) ∩ ω(g) is always empty.