In conditional asymptotic notation, “Θ(f(n)) if g(n)” indicates that the…

Concept: Standard asymptotic notation states an unconditional bound — f(n) = Θ(g(n)) means constants c1, c2, n0 exist such that c1·g(n) ≤ f(n) ≤ c2·g(n) for every n ≥ n0. Conditional asymptotic notation (used, e.g., by Brassard & Bratley as O(f(n) | C(n))) restricts that same bound to only the inputs of size n that satisfy a stated Boolean predicate/condition C — the "if C" clause attaches a case condition to the bound; it does not introduce a second function whose magnitude is being compared.

Application: Here the predicate is written g(n), so the informal statement "Θ(f(n)) if g(n)" asserts: for inputs of size n where the predicate g(n) holds (evaluates to true), the algorithm's running time is both upper- and lower-bounded, up to constants, by f(n). The "if g(n)" clause is a truth condition on g(n), not a size relation between g(n) and f(n) — so the bound applies precisely when g(n) is true.

Cross-check — contrasting the other readings:

• "g(n) is a lower bound on f(n)" treats g(n) as a comparison function against f(n) — that is the defining relation of the one-sided notation f(n) = Ω(g(n)), an unconditional two-function magnitude bound, not a case-condition predicate.

• "g(n) is an upper bound on f(n)" likewise treats g(n) as a comparison function against f(n) — the defining relation of f(n) = O(g(n)), again an unconditional two-function magnitude bound rather than a Boolean case condition.

• "g(n) is false" keeps g(n) as a Boolean predicate but inverts which truth value triggers the bound; the conditional clause "if g(n)" is satisfied by g(n) holding (being true), not by its negation.