SKEDSOFT

As an example, consider any quadratic function f(n) = an2 bn c, where a, b, and c are constants and a > 0. Throwing away the lower-order terms and ignoring the constant yields f(n) = Θ(n2). Formally, to show the same thing, we take the constants c1 = a/4, c2 = 7a/4, and. The reader may verify that 0 ≤ c1n2 ≤ an2 bn c ≤ c2n2 for all n ≥ n0. In general, for any polynomial, where the ai are constants and ad > 0, we have p(n) = Θ(nd) (see Problem 3-1).

Since any constant is a degree-0 polynomial, we can express any constant function as Θ(n0), or Θ(1). This latter notation is a minor abuse, however, because it is not clear what variable is tending to infinity. We shall often use the notation Θ(1) to mean either a constant or a constant function with respect to some variable.

O-notation: The Θ-notation asymptotically bounds a function from above and below. When we have only an asymptotic upper bound, we use O-notation. For a given function g(n), we denote by O(g(n)) (pronounced "big-oh of g of n" or sometimes just "oh of g of n") the set of functions

O(g(n)) = {f(n): there exist positive constants c and n0 such that 0 ≤ f(n) ≤ cg(n) for all n ≥ n0}.

• We use O-notation to give an upper bound on a function, to within a constant factor. Figure 3.1(b) shows the intuition behind O-notation. For all values n to the right of n0, the value of the function f(n) is on or below g(n).
• We write f(n) = O(g(n)) to indicate that a function f(n) is a member of the set O(g(n)). Note that f(n) = Θ(g(n)) implies f(n) = O(g(n)), since Θ-notation is a stronger notion than O-notation. Written set-theoretically, we have Θ(g(n)) ⊆O(g(n)). Thus, our proof that any quadratic function an2 bn c, where a > 0, is in Θ(n2) also shows that any quadratic function is in O(n2). What may be more surprising is that any linear function an b is in O(n2), which is easily verified by taking c = a |b| and n0 = 1.
• Some readers who have seen O-notation before may find it strange that we should write, for example, n = O(n2). In the literature, O-notation is sometimes used informally to describe asymptotically tight bounds, that is, what we have defined using Θ-notation. In this book, however, when we write f(n) = O(g(n)), we are merely claiming that some constant multiple of g(n) is an asymptotic upper bound on f(n), with no claim about how tight an upper bound it is. Distinguishing asymptotic upper bounds from asymptotically tight bounds has now become standard in the algorithms literature.
• Using O-notation, we can often describe the running time of an algorithm merely by inspecting the algorithm's overall structure. For example, the doubly nested loop structure of the insertion sort algorithm immediately yields an O(n2) upper bound on the worst-case running time: the cost of each iteration of the inner loop is bounded from above by O(1) (constant), the indices i and j are both at most n, and the inner loop is executed at most once for each of the n2 pairs of values for i and j.
• Since O-notation describes an upper bound, when we use it to bound the worst-case running time of an algorithm, we have a bound on the running time of the algorithm on every input. Thus, the O(n2) bound on worst-case running time of insertion sort also applies to its running time on every input. The Θ(n2) bound on the worst-case running time of insertion sort, however, does not imply a Θ(n2) bound on the running time of insertion sort on every input. For example, when the input is already sorted, insertion sort runs in Θ(n) time.
• Technically, it is an abuse to say that the running time of insertion sort is O(n2), since for a given n, the actual running time varies, depending on the particular input of size n. When we say "the running time is O(n2)," we mean that there is a function f(n) that is O(n2) such that for any value of n, no matter what particular input of size n is chosen, the running time on that input is bounded from above by the value f(n). Equivalently, we mean that the worst-case running time is O(n2).

Ω-notation: Just as O-notation provides an asymptotic upper bound on a function, Ω-notation provides an asymptotic lower bound. For a given function g(n), we denote by Ω(g(n)) (pronounced "big-omega of g of n" or sometimes just "omega of g of n") the set of functions

Ω(g(n)) = {f(n): there exist positive constants c and n₀ such that 0 ≤ cg(n) ≤ f(n) for all n ≥ n₀}.

The intuition behind Ω-notation is shown in Figure 3.1(c). For all values n to the right of n₀, the value of f(n) is on or above cg(n).

Theorem 3.1: For any two functions f(n) and g(n), we have f(n) = Θ(g(n)) if and only if f(n) = O(g(n)) and f(n) = Ω(g(n)).

As an example of the application of this theorem, our proof that an2 bn c = Θ(n2) for any constants a, b, and c, where a > 0, immediately implies that an2 bn c = Ω(n2) and an2 bn c = O(n2). In practice, rather than using Theorem 3.1 to obtain asymptotic upper and lower bounds from asymptotically tight bounds, as we did for this example, we usually use it to prove asymptotically tight bounds from asymptotic upper and lower bounds.

Since Ω-notation describes a lower bound, when we use it to bound the best-case running time of an algorithm, by implication we also bound the running time of the algorithm on arbitrary inputs as well. For example, the best-case running time of insertion sort is Ω(n), which implies that the running time of insertion sort is Ω(n).

The running time of insertion sort therefore falls between Ω(n) and O(n2), since it falls anywhere between a linear function of n and a quadratic function of n. Moreover, these bounds are asymptotically as tight as possible: for instance, the running time of insertion sort is not Ω(n2), since there exists an input for which insertion sort runs in Θ(n) time (e.g., when the input is already sorted). It is not contradictory, however, to say that the worst-case running time of insertion sort is Ω(n2), since there exists an input that causes the algorithm to take Ω(n2) time. When we say that the running time (no modifier) of an algorithm is Ω(g(n)), we mean that no matter what particular input of size n is chosen for each value of n, the running time on that input is at least a constant times g(n), for sufficiently large n.