The running time of an algorithm is \(𝑂(𝑔(𝑛))\) if and only if

Formal definition: A function T(n) is O(g(n)) if there exist constants c > 0 and n0 such that for every n ≥ n0 we have T(n) ≤ c·g(n).

Interpretation:

• This is an asymptotic upper bound on the running-time function T(n). When applied to an algorithm, it commonly refers to the worst-case running time, because that is the function one often wants to bound from above.

• There is no requirement that the best-case running time be Ω(g(n)). The best-case can be much smaller than g(n) and still the algorithm's running time can be O(g(n)).

Counterexample:

• An algorithm with best-case time 1 and worst-case time n^2 has worst-case running time O(n^2), but its best-case is not Ω(n^2). This shows the best-case need not be a lower bound of order g(n).

Conclusion: The correct condition for saying the running time is O(g(n)) is simply that the running-time function T(n) satisfies T(n) ≤ c·g(n) for sufficiently large n (for some constants c and n0). None of the provided answer choices exactly states only this requirement without adding incorrect or irrelevant conditions.