Discrete Mathematics for Computer Science

Subsection 16.2.1 A First Basic Example

Consider the homogeneous first-order linear relation without constant coefficients, \(S(n) - n S(n - 1) = 0\text{,}\) \(n \geq 1\text{,}\) with initial condition \(S(0) = 1\text{.}\) Upon close examination of this relation, we see that the \(n\)th term is \(n\) times the \((n - 1)^{st}\) term, which is a property of \(n\) factorial. \(S(n) = n!\) is a solution of this relation, for if \(n \geq 1\text{,}\)

In addition, since \(0! = 1\text{,}\) the initial condition is satisfied. It should be pointed out that from a computational point of view, our “solution” really isn't much of an improvement since the exact calculation of \(n!\) takes \(n-1\) multiplications.

If we examine a similar relation, \(G(k) - 2 ^k G(k - 1),\) \(k\geq 1\) with \(G(0) = 1\text{,}\) a table of values for \(G\) suggests a possible solution:

The exponent of 2 in \(G(k)\) is growing according to the relation \(E(k) = E(k - 1) + k,\) with \(E(0) = 0\text{.}\) Thus \(E(k)=\frac{k(k+1)}{2}\) and \(G(k) = 2^{k(k+1)/2}\text{.}\) Note that \(G(k)\) could also be written as \(2^0 2^1 2^2 \cdots 2^k\text{,}\) for \(k \geq 0\text{,}\) but this is not a closed form expression.

In general, the relation \(P(n) = f(n)P(n - 1)\) for \(n \geq 1\) with \(P(0) =f(0)\text{,}\) where \(f\) is a function that is defined for all \(n\geq 0\text{,}\) has the “solution”

This product form of \(P(n)\) is not a closed form expression because as \(n\) grows, the number of multiplications grow. Thus, it is really not a true solution. Often, as for \(G(k)\) above, a closed form expression can be derived from the product form.

Subsection 16.2.2 An Analysis of the Binary Search Algorithm

Subsubsection 16.2.2.1 Review of Logarithms

¶

Any discussion of logarithms must start by establishing a base, which can be any positive number other than 1. With the exception of Theorem 5, our base will be 2. We will see that the use of a different base (10 and \(e\approx 2.171828\) are the other common ones) only has the effect of multiplying each logarithm by a constant. Therefore, the base that you use really isn't very important. Our choice of base 2 logarithms is convenient for the problems that we are considering.

Definition 16.2.1. Base 2 logarithm.

The base 2 logarithm of a positive number represents an exponent and is defined by the following equivalence for any positive real numbers \(a\text{.}\)

\begin{equation*} \log_2 a = x \quad \Leftrightarrow \quad 2^x= a\text{.} \end{equation*}

For example, \(\log_2 8 = 3\) because \(2^3 = 8\) and \(\log_21.414\approx 0.5\) because \(2^{0.5}\approx 1.414\text{.}\) A graph of the function \(f(x) = \log_2 x\) in Figure 16.2.2 shows that if \(a < b\text{,}\) the \(\log_2a < \log_2 b\text{;}\) that is, when \(x\) increases, \(\log_2 x\) also increases. However, if we move \(x\) from \(2^{10} = 1024\) to \(2^{11} = 2048\text{,}\) \(\log_2 x\) only increases from 10 to 11. This slow rate of increase of the logarithm function is an important point to remember. An algorithm acting on \(n\) pieces of data that can be executed in \(\log_2{n}\) time units can handle significantly larger sets of data than an algorithm that can be executed in \(n/100\) or \(\sqrt{n}\) time units. The graph of \(T(n)=\left\lfloor \log_2n\right\rfloor +1\) would show the same behavior.

A few more properties that we will use in subsequent discussions involving logarithms are summarized in the following theorem.

Theorem 16.2.3. Fundamental Properties of Logarithms.

Let \(a\) and \(b\) be positive real numbers, and \(r\) a real number.

\begin{gather} \log_2 1 = 0\label{eq-log-prop-1}\tag{16.2.4}\\ \log_2 a b = \log_2a + \log_2b\label{eq-log-prop-2}\tag{16.2.5}\\ \log_2 \frac{a}{b}= \log_2a - \log_2b\label{eq-log-prop-3}\tag{16.2.6}\\ \log_2a^r = r \log_2a\label{eq-log-prop-4}\tag{16.2.7}\\ 2^{\log_2a}= a\label{eq-log-prop-5}\tag{16.2.8} \end{gather}

Definition 16.2.4. Logarithms base \(b\).

If \(b > 0\text{,}\) \(b \neq 1\text{,}\) then for \(a>0\text{,}\)

\begin{equation*} \log_b a = x\Leftrightarrow b^x= a \end{equation*}

Theorem 16.2.5. How logarithms with different bases are related.

Let \(b>0\text{,}\) \(b \neq 1\text{.}\) Then for all \(a >0\text{,}\) \(\log_b a = \frac{\log_2a}{\log_2b}\text{.}\) Therefore, if \(b > 1\text{,}\) base b logarithms can be computed from base 2 logarithms by dividing by the positive scaling factor \(\log_2b\text{.}\) If \(b < 1\text{,}\) this scaling factor is negative.

Proof.

By an analogue of (16.2.8), \(a=b^{\log_b a}\text{.}\) Therefore, if we take the base 2 logarithm of both sides of this equality we get:

\begin{equation*} \log_2 a = \log_2 \left(b^{\log_b a}\right) \Rightarrow \log_2 a =\log_b a \cdot \log_2 b \end{equation*}

Finally, divide both sides of the last equation by \(\log_2b\text{.}\)

Note 16.2.6.

\(\log_210 \approx 3.32192\) and \(\log_2e = 1.55269\text{.}\)

Subsection 16.2.3 Analysis of Bubble Sort and Merge Sort

The efficiency of any search algorithm such as the binary search relies on fact that the search list is sorted according to a key value and that the search is based on the key value. There are several methods for sorting a list. One example is the bubble sort. You might be familiar with this one since it is a popular “first sorting algorithm.” A time analysis of the algorithm shows that if \(B(n)\) is the worst-case time needed to complete the bubble sort on \(n\) items, then \(B(n) =(n-1) + B(n-1)\) and \(B(1) = 0\text{.}\) The solution of this relation is a quadratic function \(B(n) =\frac{1}{2}\left(n^2-n\right)\text{.}\) The growth rate of a quadratic function such as this one is controlled by its squared term. Any other terms are dwarfed by it as \(n\) gets large. For the bubble sort, this means that if we double the size of the list that we are to sort, \(n\) changes to \(2n\) and so \(n^2\) becomes \(4n^2\) . Therefore, the time needed to do a bubble sort is quadrupled. One alternative to bubble sort is the merge sort. Here is a simple version of this algorithm for sorting \(F=\{r(1), r(2), \ldots , r(n)\}\text{,}\) \(n \geq 1\text{.}\) If \(n = 1\text{,}\) the list is sorted trivially. If \(n\geq 2\) then:

1. Divide \(F\) into \(F_1= \{r(1), \ldots , r(\lfloor n/2\rfloor )\}\) and \(F_2= \{r(\lfloor n/2\rfloor +1), \ldots ,r(n)\}\text{.}\)

2. Sort \(F_1\) and \(F_2\) using a merge sort.

3. Merge the sorted lists \(F_1\) and \(F_2\) into one sorted list. If the sort is to be done in descending order of key values, you continue to choose the higher key value from the fronts of \(F_1\) and \(F_2\) and place them in the back of \(F\text{.}\)

Note that \(F_1\) will always have \(\lfloor n/2\rfloor\) items and \(F_2\) will have \(\lceil n/2\rceil\) items; thus, if \(n\) is odd, \(F_2\) gets one more item than \(F_1\text{.}\) We will assume that the time required to perform Step 1 of the algorithm is insignificant compared to the other steps; therefore, we will assign a time value of zero to this step. Step 3 requires roughly \(n\) comparisons and \(n\) movements of items from \(F_1\) and \(F_2\) to \(F\text{;}\) thus, its time is proportional to \(n\text{.}\) For this reason, we will assume that Step 3 takes \(n\) time units. Since Step 2 requires \(T(\lfloor n/2\rfloor ) + T(\lceil n/2\rceil )\) time units,

with the initial condition

Instead of an exact solution of these equations, we will be content with an estimate for \(T(n)\text{.}\) First, consider the case of \(n=2^r\text{,}\) \(r \geq 1\text{:}\)

Thus, if \(n\) is a power of 2, \(T(n) = n \log_2 n\text{.}\) Now if, for some \(r \geq 2\text{,}\) \(2^{r-1}\leq n\leq 2^r\text{,}\) then \((r-1)2^{r-1}\leq T(n) < r 2^r\text{.}\) This can be proved by induction on \(r\text{.}\) As \(n\) increases from \(2^{r-1}\) to \(2^r\text{,}\) \(T(n)\) increases from \((r-1)2^{r-1}\)to \(r 2^r\) and is slightly larger than \(\left\lfloor n \log_2n\right\rfloor\text{.}\) The discrepancy is small enough so that \(T_e(n)=\left\lfloor n \log _2n\right\rfloor\) can be considered a solution of (16.2.9) and (16.2.10) for the purposes of comparing the merge sort with other algorithms. Table 16.2.7 compares \(B(n)\) with \(T_e(n)\) for selected values of \(n\text{.}\)

Subsection 16.2.4 Derangements

A derangement is a permutation on a set that has no “fixed points”. Here is a formal definition:

If \(A = \{1, 2, . . . , n\}\text{,}\) an interesting question might be “How many derangements are there of \(A\text{?}\)” We know that our answer is bounded above by \(n!\text{.}\) We can also expect our answer to be quite a bit smaller than \(n!\) since \(n\) is the image of itself for \((n-1)!\) of the permutations of \(A\text{.}\)

Let \(D(n)\) be the number of derangements of \(\{1, 2, . . . , n\}\text{.}\) Our answer will come from discovering a recurrence relation on \(D\text{.}\) Suppose that \(n \geq 3\text{.}\) If we are to construct a derangement of \(\{1, 2, \dots , n\}\text{,}\) \(f\text{,}\) then \(f(n) = k \neq n\text{.}\) Thus, the image of \(n\) can be selected in \(n-1\) different ways. No matter which of the \(n -1\) choices we make, we can complete the definition of \(f\) in one of two ways. First, we can decide to make \(f(k) = n\text{,}\) leaving \(D(n -2)\) ways of completing the definition of \(f\text{,}\) since \(f\) will be a derangement of \(\{1, 2, \dots ,n\} - \{n, k\}\text{.}\) Second, if we decide to select \(f(k)\neq n\text{,}\) each of the \(D(n - 1)\) derangements of \(\{1, 2,\dots ,n-1\}\) can be used to define \(f\text{.}\) If \(g\) is a derangement of \(\{1, 2, \dots , n-1\}\) such that \(g(p) = k\text{,}\) then define f by

Note that with our second construction of \(f\text{,}\) \(f(f(n)) = f(k) \neq n\text{,}\) while in the first construction, \(f(f(n)) = f(k) = n\text{.}\) Therefore, no derangement of \(\{1, 2, . . . , n\}\) with \(f(n) = k\) can be constructed by both methods.

To recap our result, we see that \(f\) is determined by first choosing one of \(n - 1\) images of \(n\) and then constructing the remainder of \(f\) in one of \(D(n - 2) + D(n -1)\) ways. Therefore,

This homogeneous second-order linear relation with variable coefficients, together with the initial conditions \(D(1) = 0\) and \(D(2) = 1\text{,}\) completely defines \(D\text{.}\) Instead of deriving a solution of this relation by analytical methods, we will give an empirical derivation of an approximation of \(D(n)\text{.}\) Since the derangements of \(\{1,2 . . . , n\}\) are drawn from a pool of \(n!\) permutations, we will see what percentage of these permutations are derangements by listing the values of \(n!\text{,}\) \(D(n)\text{,}\) and \(\frac{D(n)}{n!}\text{.}\) The results we observe will indicate that as \(n\) grows, \(\frac{D(n)}{n!}\) hardly changes at all. If this quotient is computed to eight decimal places, for \(n \geq 12\text{,}\) \(D(n)/n! = 0.36787944\text{.}\) The reciprocal of this number, which \(D(n)/n!\) seems to be tending toward, is, to eight places, 2.7182818. This number appears in so many places in mathematics that it has its own name, \(e\text{.}\) An approximate solution of our recurrence relation on \(D\) is then \(D(n)\approx \frac{n!}{e}\text{.}\)