## 1.4 Order We just illustrated that an algorithm with a time complexity of *n* is more efficient than one with a time complexity of *n*2 for sufficiently large values of *n*, regardless of how long it takes to process the basic operations in the two algorithms. Suppose now that we have two algorithms for the same problem and that their every-case time complexities are 100*n* for the first algorithm and 0.01*n*2 for the second algorithm. Using an argument such as the one just given, we can show that the first algorithm will eventually be more efficient than the second one. For example, if it takes the same amount of time to process the basic operations in both algorithms and the overhead is about the same, the first algorithm will be more efficient if  Dividing both sides by 0.01*n* yields  If it takes longer to process the basic operation in the first algorithm than in the second, then there is simply some larger value of *n* at which the first algorithm becomes more efficient. Algorithms with time complexities such as *n* and 100*n* are called ***lineartime algorithms*** because their time complexities are linear in the input size *n*, whereas algorithms with time complexities such as *n*2 and O.01*n*2 are called ***quadratic-time algorithms*** because their time complexities are quadratic in the input size *n*. There is a fundamental principle here. That is, *any linear-time algorithm is eventually more efficient than any quadratic-time algorithm.* In the theoretical analysis of an algorithm, we are interested in eventual behavior. Next we will show how algorithms can be grouped according to their eventual behavior. In this way we can readily determine whether one algorithm's eventual behavior is better than another's. ### 1.4.1 An Intuitive Introduction to Order Functions such as 5*n*2 and 5*n*2 + 100 are called ***pure quadratic*** functions because they contain no linear term, whereas a function such as 0. 1*n*2 + *n* + 100 is called a ***complete quadratic*** function becanse it contains a linear term. [Table 1.3](#ch01table03) shows that eventually the quadratic term dominates this function. That is, the values of the other terms eventually become insignificant compared with the value of the quadratic term. Therefore, although the function is not a pure quadratic function, we can classify it with the pure quadratic functions. This means that if some algorithm has this time complexity, we can call the algorithm a quadratic-time algorithm. Intuitively, it seems that we should always be able to throw away low-order terms when classifying complexity functions. For example, it seems that we should be able to classify 0.1*n*3 + 10*n*2 + 5*n* + 25 with pure cubic functions. We will soon establish rigorously that we can do this. First let's try to gain an intuitive feel for how complexity functions are classified. Table 1.3: The quadratic term eventually dominates*n* 0\.1*n*2 0\.1*n*2 + *n* + 100 10 10 120 20 40 160 50 250 400 100 1,000 1,200 1,000 100,000 101,100 The set of all complexity functions that can be classified with pure quadratic functions is called Θ(*n*2), where Θ is the Greek capital letter "theta." If a function is a member of the set Θ(*n*2), we say that the function is order of *n*2. For example, because we can throw away low-order terms,  which means that *g*(*n*) is order of *n*2. As a more concrete example, recall from [Section 1.3.1](LiB0010.html#58) that the time complexity for [Algorithm 1.3](LiB0008.html#32) (Exchange Sort) is given by *T*(*n*) = *n*(*n* − 1)/2. Because  throwing away the lower-order term *n*/2 shows that *T*(*n*) ∊ Θ(*n*2). When an algorithm's time complexity is in Θ(*n*2), the algorithm is called a ***quadratic-time algorithm*** or a **Θ(*n*2) algorithm.** We also say that the algorithm is Θ(*n*2). Exchange Sort is a quadratic-time algorithm. Similarly, the set of complexity functions that can be classified with pure cubic functions is called Θ(*n*3), and functions in that set are said to be order of *n*3, and so on. We will call these sets ***complexity categories.*** The following are some of the most common complexity categories:  In this ordering, if *f*(*n*) is in a category to the left of the category containing *g*(*n*), then *f*(*n*) eventually lies beneath *g*(*n*) on a graph. [Figure 1.3](#ch01fig03) plots the simplest members of these categories: *n*, ln *n*, *n* ln *n*, and so on. [Table 1.4](#ch01table04) shows the execution times of algorithms whose time complexities are given by these functions. The simplifying assumption is that it takes 1 nanosecond (10-9 second) to process the basic operation for each algorithm. The table shows a possibly surprising result. One might expect that as long as an algorithm is not an exponential-time algorithm, it will be adequate. However, even the quadratictime algorithm takes 31.7 years to process an instance with an input size of 1 billion. On the other hand, the Θ(*n* ln *n*) algorithm takes only 29.9 seconds to process such an instance. Ordinarily an algorithm has to be Θ(*n* ln *n*) or better for us to assume that it can process extremely large instances in tolerable amounts of time. This is not to say that algorithms whose time complexities are in the higher-order categories are not useful. Algorithms with quadratic, cubic, and even higher-order time complexities can often handle the actual instances that arise in many applications. [](fig1-3_0.jpg) Figure 1.3: • Growth rates of some common complexity functions. Table 1.4: Execution times for algorithms with the given time complexities*n* *f*(*n*) = *lg n* *f*(*n*) = *n* *f*(*n*) = *n lg n* *f*(*n*) = *n*2 *f*(*n*) = *n*3 *f*(*n*) = 2n 10 0\.003 μs\[[\*](#ftn.ch01fnt01)\] 0\.01 μs 0\.033 μs 0\.10 μs 1\.0 μs 1 μs 20 0\.004 μs 0\.02 μs 0\.086 μs 0\.40 μs 8\.0 μs 1 ms\[[†](#ftn.ch01fnt02)\] 30 0\.005 μs 0\.03 μs 0\.147 μs 0\.90 μs 27\.0 μs 1 s 40 0\.005 μs 0\.04 μs 0\.213 μs 1\.60 μs 64\.0 μs 18\.3 min 50 0\.006 μs 0\.05 μs 0\.282 μs 2\.50 μs 125\.0 μs 13 days 102 0\.007 μs 0\.10 μs 0\.664 μs 10\.00 μs 1\.0 ms 4 × 1013 years 103 0\.010 μs 1\.00 μs 9\.966 μs 1\.00 ms 1\.0 s 104 0\.013 μs 10\.00 μs 130\.000 μs 100\.00 ms 16\.7 min 105 0\.017 μs 0\.10 ms 1\.670 ms 10\.00 s 11\.6 days 106 0\.020 μs 1\.00 ms 19\.930 ms 16\.70 min 31\.7 years 107 0\.023 μs 0\.01 s 2\.660 s 1\.16 days 31,709 years 108 0\.027 μs 0\.10 s 2\.660 s 115\.70 days 3\.17 × 107 years 109 0\.030 μs 1\.00 s 29\.900 s 31\.70 years \[[\*](#ch01fnt01)\]1 ns = 10-9 second. \[[†](#ch01fnt02)\]1 ms = 10−3 second. Before ending this discussion, we stress that there is more information in knowing a time complexity exactly than in simply knowing its order. For example, recall the hypothetical algorithms, discussed earlier, that have time complexities of 100*n* and 0.01*n*2. If it takes the same amount of time to process the basic operations and execute the overhead instructions in both algorithms, then the quadratic-time algorithm is more efficient for instances smaller than 10,000. If the application never requires instances larger than this, the quadratic-time algorithm should be implemented. If we knew only that the time complexities were in Θ(*n*) and Θ(*n*2), respectively, we would not know this. The coefficients in this example are extreme, and in practice they are often less extreme. Furthermore, there are times when it is quite difficult to determine the time complexities exactly. Therefore, we are sometimes content to determine only the order. ### 1.4.2 A Rigorous Introduction to Order The previous discussion imparted an intuitive feel for order (Θ). Here we develop theory that enables us to define order rigorously. We accomplish this by presenting two other fundamental concepts. The first is "big *O*." Definition For a given complexity function *f*(*n*), *O*(*f*(*n*)) is the set of complexity functions *g*(*n*) for which there exists some positive real constant *c* and some nonnegative integer *N* such that for all *n* ≤ *N*,  If *g*(*n*) ∊ *O*(*f*(*n*)), we say that *g*(*n*) is ***big O*** of *f*(*n*). [Figure 1.4(a)](#ch01fig04) illustrates "big *O*." Although *g*(*n*) starts out above *cf*(*n*) in that figure, eventually it falls beneath *cf*(*n*) and stays there. [Figure 1.5](#ch01fig05) shows a concrete example. Although *n*2 + 10*n* is initially above 2*n*2 in that figure, for *n* ≤ 10  [](fig1-4_0.jpg) Figure 1.4: Illustrating "big *O*," Ω, and Θ. [](fig1-5_0.jpg) Figure 1.5: The function *n*2 + 10*n* eventually stays beneath the function 2*n*2. We can therefore take *c* = 2 and *N* = 10 in the definition of “big *O*  If, for example, *g*(*n*) is in *O*(*n*2), then eventually *g*(*n*) lies beneath some pure quadratic function *cn*2 on a graph. This means that if *g*(*n*) is the time complexity for some algorithm, eventually the running time of the algorithm will be at least as fast as quadratic. For the purposes of analysis, we can say that eventually *g*(*n*) is at least as *good* as a pure quadratic function. "Big *O*" (and other concepts that will be introduced soon) are said to describe the **asymptotic** behavior of a function because they are concerned only with eventual behavior. We say that "big *O*" puts an ***asymptotic upper bound*** on a function. The following examples illustrate how to show "big *O*." Example 1.7****We show that 5*n*2∊ *O*(*n*2). Because, for *n* ≤ 0,  we can take *c* = 5 and *N* = 0 to obtain our desired result. **** Example 1.8****Recall that the time complexity of [Algorithm 1.3](LiB0008.html#32) (Exchange Sort) is given by  Because, for *n* ≥ 0,  we can take *c* = 1/2 and *N* = 0 to conclude that *T*(*n*) ∊ *O*(*n*2). **** A difficulty students often have with "big *O*" is that they erroneously think there is some unique *c* and unique *N* that must be found to show that one function is "big *O*" of another. This is not the case at all. Recall that Figure 1\.5 illustrates that *n*2 + 10*n*∊ O(*n*2 using *c = 2* and *N = 10*. Alternatively, we could show it as follows. Example 1.9****We show that *n*2 + 10*n* ∊ *O*(*n*2). Because, for *n* ≥ 1,  we can take *c* = 11 and *N* = 1 to obtain our result. **** In general, one can show "big *O*" using whatever manipulations seem most straightforward. Example 1.10****We show that *n*2∊ O(*n*2 + 10*n*). Because, for *n* ≥ 0,  we can take *c* = 1 and *N* = 0 to obtain our result. **** The purpose of this last example is to show that the function inside "big O" does not have to be one of the simple functions plotted in [Figure 1.3](#ch01fig03). It can be any complexity function. Ordinarily, however, we take it to be a simple function like those plotted in [Figure 1.3](#ch01fig03). Example 1.11****We show that *n* ∊ (*n* 2). Because, for *n* ≥ 1,  we can take *c* = 1 and *N* = 1 to obtain our result. **** This last example makes a crucial point about "big *O*". A complexity function need not have a quadratic term to be in O(*n*2). It need only eventually lie beneath some pure quadratic function on a graph. Therefore, any logarithmic or linear complexity function is in O(*n*2). Similarly, any logarithmic, linear, or quadratic complexity function is in O(*n*3), and so on. [Figure 1.6(a)](#ch01fig06) shows some exemplary members of O(*n*2). [](fig1-6_0.jpg) Figure 1.6: The sets O (*n*2), O (*n*2, O (*n*2). Some exemplary members are shown. Just as "big O" puts an asymptotic upper bound on a complexity function, the following concept puts an ***asymptotic lower bound*** on a complexity function. Definition For a given complexity function *f(n)*, Ω (*f(n)*) is the set of complexity functions *g(n)* for which there exists some positive real constant *c* and some nonnegative integer *N* such that, for all *n* ≥ *N*,  The symbol Ω is the Greek capital letter "omega." If *g(n)* ∊Ω (*f(n)*), we say that *g(n)* is ***Omega*** of *f*(*n*). [Figure 1.4(b)](#ch01fig04) illustrates Ω. Some examples follow. Example 1.12****We show that 5*n*2. Because, for *n*≥0,  we can take *c* = 1 and *N* = 0 to obtain our result. **** Example 1.13****We show that *n*2 + 10*n* ∊ Ω (*n*2. Because, for *n* ≥ 0,  we can take *c* = 1 and *N* = 0 to obtain our result. **** Example 1.14****Consider again the time complexity of [Algorithm 1.3](LiB0008.html#23) (Exchange Sort). We show that  For *n* ≥ 2,  Therefore, for *n* ≥ 2,  which means we can take *c* = 1/4 and *N* = 2 to obtain our result. **** As is the case for "big *O*," there are no unique constants *c* and *N* for which the conditions in the definition of Ω hold. We can choose whichever ones make our manipulations easiest. If a function is in Ω (*n*2), then eventually the function lies above some pure quadratic function on a graph. For the purposes of analysis, this means that eventally it is least as *bad* as a pure quadratic function. However, as the following example illustrates, the function need not be a quadratic function. Example 1.15****We show that *n*3∊ Ω(*n*2). Because, if *n* ≥ 1,  we can take *c* = 1 and *N* = 1 to obtain our result. **** [Figure 1.6(b)](#ch01fig06) shows some exemplary members of Ω (*n*2. If a function is in both *O*(*n*2) and Ω (*n*2), we can conclude that eventually the function lies beneath some pure quadratic function on a graph and eventually it lies above some pure quadratic function on a graph. That is, eventually it is at least as *good* as some pure quadratic function and eventually it is at least as bad as some pure quadratic function. We can therefore conclude that its growth is similar to that of a pure quadratic function. This is precisely the result we want for our rigorous notion of order. We have the following definition. Definition For a given complexity function *f*(*n*),  This means that Θ (*f*(*n*)) is the set of complexity functions *g*(*n*) for which there exists some positive real constants *c* and *d* and some nonnegative integer *N* such that, for all *n*≥ *N*,  If *g*(*n*) ∊ Θ (*f*(*n*)), we say that *g*(*n*) is ***order*** of *f*(*n*). Example 1.16****Consider once more the time complexity of [Algorithm 1.3](LiB0008.html#32). [Examples 1.8](#ch01ex22) and [1.14](#ch01ex28) together establish that  This means that *T*(*n*) ∊ O (*n*2) = Θ (*n*2) = Θ(*n*2) **** [Figure 1.6(c)](#ch01fig06) depicts that Θ(*n*2) is the intersection of O(*n*2) and Ω(*n*2), whereas [Figure 1.4](#ch01fig04)(*c*) illustrates Θ. Notice in [Figure 1.6](#ch01fig06)(*c*) that the function 5*n* + 7 is not in Ω (*n*2), and the function 4*n*3 + 3*n*2 is not in O (*n*2). Therefore, neither of these functions is in Θ(*n*2). Although intuitively this seems correct, we have not yet proven it. The following example show how such a proof proceeds. Example 1.17****We shows that *n* is not in Ω(*n*2) by using ***proof by contradiction.***. In this type of proof we assume something is true—in this case, that *n* ∊Ω(*n*2—and then we do manipulations that lead to a result that is not true. That is, the result *contradicts* something known to be true. We then conclude that what we assumed in the first place cannot be true. Assuming that *n* ∊ Ω (*n*2) means we are assuming that there exists some positive constant *c* and some nonnegative integer *N* such that, for *n*≤*N*,  If we divide both sides of this inequality by *cn*, we have, for *n*≥*N*,  However, for any *n* > 1/*c*, this inequality cannot hold, which means that it cannot hold for all *n*≥*N*. This contradiction proves that *n* is not in ≥ *n*2. **** We have one more definition concerning order that expresses relationships such as the one between the function *n* and the function *n*2. Definition For a given complexity function *f*(*n*), o(*f*(*n*)) is the set of all complexity functions *g*(*n*) satisfying the following: For every positive real constant *c* there exists a nonnegative integer *N* such that, for all *n*≥*N*,  If *g*(*n*)∊ o(*f*(*n*)), we say that *g*(*n*), is ***small*** o of *f*(*n*). Recall that "big O" means there must be *some* real positive constant *c* for which the bound holds. This definition says that the bound must hold for *every* real positive constant *c*. Because the bound holds for every positive *c*, it holds for arbitrarily small *c*. For example, if *g*(*n*) ∊ o(*f*(*n*)), there is an *N* such that, for *n*> *N*,  We see that *g*(*n*) becomes insignificant relative to *f*(*n*) as *n* becomes large. For the purposes of analysis, if *g*(*n*) is in o(*f*(*n*) is eventually much *better* than functions such as *f*(*n*). The following examples illustrate this. Example 1.18****We show that  Let *c*> 0 be given. We need to find an *N* such that, for *n*≥*N*,  If we divide both sides of this inequality by *cn,*, we get  Therefore, it suffices to choose any *N* ≥ 1/*c*. Notice that the value of *N* depends on the constant *c*. For example, if *c* = 0.00001, we must take *N* equal to at least 100,000. That is, for *n* ≥ 100,000,  **** Example 1.19****We show that *n* is not in o(5*n*). We will use proof by contradiction to show this. Let *c* = 1/6. If *n* ∊ o (5*n*), then there must exist some *N* such that, for *n*≥ *N*,  This contradiction proves that *n* is not in o(5*n*). **** The following theorem relates "small o" to our other asymptotic notation. Theorem 1.2****If *g*(*n*) ∊ o (*f*(*n*)), then  That is, *g*(*n*) is in O (*f*(*n*))but is not in Ω(*f(n))*. Proof: Because *g(n)∊o(f(n))*, for every positive real constant *c* there exists an *N* such that, for all *n*∊*N*,  which means that the bound certainly holds for some *c*. Therefore,  We will show that *g*(*n*) is not Ω (*f*(*n*)) using proof by contradiction. If *g*(*n*) ∊ Ω(*f*(*n*)), then there exists some real constant *c* > 0 and some *N*1 such that, for all *n*≥*N*1,  But, because *g*(*n*) ∊ o (*f*(*n*)), there exists some *N*2 such that, for all *n* ≥ *N*2,  Both inequalities would have to hold for all *n* greater than both *N*1, *N*2. This contradiction proves that *g*(*n*) cannot be in Ω (*f*(*n*)). **** You may think that o (*f*(*n*)) and O (*f*(*n*)) – Ω (*f*(*n*)) must be the same set. This is not true. There are unusual functions that are in O (*f*(*n*)) – Ω (*f*(*n*)) but that are not in o (*f*(*n*)). The following example illustrates this. Example 1.20****Consider the function  It is left as an exercise to show that  **** [Example 1.20](#ch01ex29), of course, is quite contrived. When complexity fuctions represent the time complexities of actual algorithms, ordinarily the functions in *O*(f(n)) – Ω(f(n)) are the same ones that are in *o*(*f*(*n*)).  For example,  This means that Θ separates complexity functions into disjoint sets. We will call these sets ***complexity categories.*** Any function from a given category can represent the category. For convenience, we ordinarily represent a category by its simplest member. The previous complexity category is represented by Θ(*n*2). The time complexities of some algorithms do not increase with *n* For example, recall that the best-case time complexity *B* *n* for [Algorithm 1.1](LiB0008.html#27) is 1 for every value of *n*. The complexity category containing such functions can be represented by any constant, and for simplicity we represent it by Θ (1). The following are some important properties of order that make it easy to determine the orders of many complexity functions. They are stated without proof. The proofs of some will be derived in the exercises, whereas the proofs of others follow from results obtained in the next subsection. The second result we have already discussed. It is included here for completeness. Properties of Order: 1. *g* (*n*) ∊ *O*(*fn*)) if and only if *f(n)* ∊ Ω(*g*(*n*)). 1. *g*(*n* ∊ Θ (*f*(*n*)) if and only if *f*(*n*∊ Θ(*g*(*n*)). 1. If *b*> 1 and *a* > 1, then loga*n* ∊ Θ (logb*n*). This implies that all logarithmic complexity functions are in the same complexity category. We will represent this category by Θ(lg*n*). 1. If *b* > *a* > 0, then  This implies that all exponential complexity functions are not in the same complexity category. 1. For all *a* > 0  This implies that *n!* is *worse* than any exponential complexity function. 1. Consider the following ordering of complexity categories:  where *k* > *j* and *b* > *a* 1. If a complexity function *g*(*n*), is in a category that is to the left of the category containing *f*(*n*), then  1. If *c* ≥ 0, *d* > 0, *g*(*n*), ∊*O*(f (*n*)), and *h(n)* ∊ Θ (*f*(*n*)), then  Example 1.21****Property 3 states that all logarithmic complexity functions are in the same complexity category. For example,  This means that the relationship between log4*n* and lg *n* is the same as the one between 7*n*2 + 5*n* and *n*2. **** Example 1.22****Property 6 states that any logarithmic function is eventually better than any polynomial, any polynomial is eventually better than any exponential function, and any exponential function is eventually better than the factorial function. For example,  **** Example 1.23****Properties 6 and 7 can be used repeatedly. For example, we can show that 5*n*+31*gn*+10*n* lg*n*+7*n*2∊ Θ (*n*2), as follows. Repeatedly applying Properties 6 and 7, we have  **** In practice, we do not repeatedly appeal to the properties, but rather we simply realize that we can throw out low-order terms. If we can obtain the exact time complexity of an algorithm, we can determine its order simply by throwing out low-order terms. When this is not possible, we can appeal back to the definitions of "big *O*" and Ω to determine order. For example, suppose for some algorithm we are unable to determine *T*(*n* \[or *W*(*n),* *A*(*n* or *B*(*n*)\] exactly. If we can show that > *T*(*n* ∊ *O* (*f*(*n*)) and *T*(*n* ∊ δ (*f*(*n*)) by appealing directly to the definitions, we can conclude that *T*(*n*) ∊ Θ *fn*)). Sometimes it is farily easy to show that *Tn* ∊ *O(**f*(*n*)) but difficult to determine whether *T*(*n* is in Ω *f*(*n*)). In such cases we may be content to show only that *T* ∊ *O*(*f*(*n*)), because this implies that *T*(*n*) is at least as *good* as functions such as *f*(*n*). Similarly, we may be content to learn only that *T*(*n*) ∊ Θ*(*f(*n*)), because this implies that *Tn*) is at least *as bad* as functions such as *fn* Before closing, we mention that many authors say > *f*(*n*) = Θ (*n*2 instead of ∊ Θ (*n*2). Both mean the same thing—namely, that *f*(*n)* is a member of the set Θ*n*)2). Similarly, it is common to write  You are referred to Knuth (1973) for an account of the history of "order" and to Brassard (1985) for a discussion of the definitions of order given here. Our definitions of "big *O*," Ω, and Θ are, for the most part, standard. There are, however, other definitions of "small *o*." It is not standard to call the sets Θ*n*, Θ*n*)2, and so on, "complexity categories." Some authors call them "complexity classes," although this term is used more often to refer to the sets of problems discussed in [Chapter 9](LiB0074.html#880). Other authors do not give them any particular name at all. ### 1.4.3 Using a Limit to Determine Order  We now show how order can sometimes be determined using a limit. This material is included for those familiar with limits and derivatives. Knowledge of this material is not required elsewhere in the text. Theorem 1.3****We have the following:  Proof: The proof is left as an exercise. **** Example 1.24****[Theorem 1.3](#ch01ex33) implies that  because  **** Using [Theorem 1.3](#ch01ex33) in [Example 1.24](#ch01ex34) is not very exciting because the result could have easily been established directly. The following examples are more interesting. Example 1.25****[Theorem 1.3](#ch01ex33) implies that, for *b* > *a* > 0,  The limit is 0 because 0 < *a/b* < 1. This is Property 4 in the Properties of Order (near the end of [Section 1.4.2](#ch01lev2sec7)). **** Example 1.26****[Theorem 1.3](#ch01ex33) implies that, for *a* > 0,  If *a* ≥ 1, the result is trivial. Suppose that *a* > 1. If *n* is so large that  Because *a* > 1, the implies that  This is Property 5 in the Properties of Order. **** The following theorem, whose proof can be found in most calculus texts, enhances the usefulness of [Theorem 1.3](#ch01ex33). Theorem 1.4*****L'Hôpital's Rule* If *f*(*x*) and *g*(*x*) are both differentiable with derivatives *f*'(*x*) and *g'* (*x*), respectively, and if  whenever the limit on the right exists. **** [Theorem 1.4](#ch01ex37) holds for functions of real valuables, whereas our complexity functions are functions of integer variables. However, most of our complexity functions (for example, lg *n*, *n*, etc.) are also functions of real variables. Furthermore, if a function *f*(*x*) is a function of a real variable *x*, then  where *n* is an integer, whenever the limit on the right exists. Therefore, we can apply [Theorem 1.4](#ch01ex37) to complexity analysis, as the following examples illustrate. Example 1.27****[Theorems 1.3](#ch01ex33) and [1.4](#ch01ex37) imply that  because  **** Example 1.28****[Theorems 1.3](#ch01ex33) and [1.4](#ch01ex37) imply that, for *b* > 1 and *a* > 1,  because  This is Property 3 in the Properties of Order. ****