算法导论第三版参考答案_算法导论答案

1.1-1

Give a real-world example that requires sorting or a real-world example that requires computing a convex hull.

• Sorting: browse the price of the restaurants with ascending prices on NTU street.
• Convex hull: computing the diameter of set of points.

1.1-2

Other than speed, what other measures of efficiency might one use in a real-world setting?

Memory efficiency and coding efficiency.

1.1-3

Select a data structure that you have seen previously, and discuss its strengths and limitations.

Linked-list:

• Strengths: insertion and deletion.
• Limitations: random access.

1.1-4

How are the shortest-path and traveling-salesman problems given above similar? How are they different?

• Similar: finding path with shortest distance.
• Different: traveling-salesman has more constrains.

1.1-5

Come up with a real-world problem in which only the best solution will do. Then come up with one in which a solution that is ‘‘approximately’’ the best is good enough.

• Best: find the GCD of two positive integer numbers.
• Approximately: find the solution of differential equations.

1.2-1

Give an example of an application that requires algorithmic content at the application level, and discuss the function of the algorithms involved.

Drive navigation.

1.2-2

Suppose we are comparing implementations of insertion sort and merge sort on the same machine. For inputs of size $n$ , insertion sort runs in $8n^2$ steps, while merge sort runs in $64n\lg n$ steps. For which values of $n$ does insertion sort beat merge sort?

$$\begin{align} 8n^2 & < 64n\lg n \\ 2^n & < n^8 \\ n & \le 43. \end{align}$$

1.2-3

What is the smallest value of $n$ such that an algorithm whose running time is $100n^2$ runs faster than an algorithm whose running time is $2^n$ on the same machine?

$$\begin{align} 100n^2 & < 2^n \\ n & \ge 15. \end{align}$$

For each function $f(n)$ and time $t$ in the following table, determine the largest size $n$ of a problem that can be solved in time $t$, assuming that the algorithm to solve the problem takes $f(n)$ microseconds.

For each function $f(n)$ and time $t$ in the following table, determine the largest size $n$ of a problem that can be solved in time $t$, assuming that the algorithm to solve the problem takes $f(n)$ microseconds.

2-1

Although merge sort runs in $\Theta (n\lg n)$ worst-case time and insertion sort runs in $\Theta (n^2)$ worst-case time, the constant factors in insertion sort can make it faster in practice for small problem sizes on many machines. Thus, it makes sense to coarsen the leaves of the recursion by using insertion sort within merge sort when subproblems become sufficiently small. Consider a modification to merge sort in which $n/k$ sublists of length $k$ are sorted using insertion sort and then merged using the standard merging mechanism, where $k$ is a value to be determined.

a. Show that insertion sort can sort the $n/k$ sublists, each of length $k$, in $\Theta (nk)$ worst-case time.

b. Show how to merge the sublists in $\Theta (n\lg (n/k))$ worst-case time.

c. Given that the modified algorithm runs in $\Theta (nk+n\lg (n/k))$ worst-case time, what is the largest value of $k$ as a function of $n$ for which the modified algorithm has the same running time as standard merge sort, in terms of $\Theta$-notation?

d. How should we chosse $k$ in practice?

a. Insertion sort takes $\Theta (k^2)$ time per $k$-element list in the worst case. Therefore, sorting $n/k$ lists of $k$ elements each takes $\Theta (k^{2}n/k)=\Theta (nk)$ worst-case time.

b. Just extending the $2$-list merge to merge all the lists at once would take $\Theta (n\cdot (n/k))=\Theta (n^2/k)$ time ($n$ from copying each element once into the result list, $n/k$ from examining $n/k$ lists at each step to select next item for result list).

To achieve $\Theta (n\lg (n/k))$-time merging, we merge the lists pairwise, then merge the resulting lists pairwise, and so on, until there’s just one list. The pairwise merging requires $\Theta (n)$ work at each level, since we are still working on $n$ elements, even if they are partitioned among sublists. The number of levels, starting with $n/k$ lists (with $k$ elements each) and finishing with 1 list (with $n$ elements), is $\lceil \lg (n/k)\rceil$. Therefore, the total running time for the merging is $\Theta (n\lg (n/k))$.

c. The modified algorithm has the same asymptotic running time as standard merge sort when $\Theta (nk+n\lg (n/k))=\Theta (n\lg n)$. The largest asymptotic value of $k$ as a function of $n$ that satisfies this condition is $k=\Theta (\lg n)$.

To see why, first observe that $k$ cannot be more than $\Theta (\lg n)$ (i.e., it can’t have a higher-order term than $\lg n$), for otherwise the left-hand expression wouldn’t be $\Theta (n\lg n)$ (because it would have a higher-order term than $n\lg n$). So all we need to do is verify that $k=\Theta (\lg n)$ works, which we can do by plugging $k=\lg n$ into

$$\Theta (nk+n\lg (n/k))=\Theta (nk+n\lg n-n\lg k)$$

to get

$$\Theta (n\lg n+n\lg n-n\lg \lg n)=\Theta (2n\lg n-n\lg \lg n),$$

which by taking just the high-order term and ignorin the constant coefficient, equals $\Theta (n\lg n)$.

d. In practice, $k$ should be the largest list length on which insertion sort is faster than merge sort.

2-2

Bubblesort is a popular, but inefficient, sorting algorithm. It works by repeatedly swapping adjacent elements that are out of order.

BUBBLESORT(A)
    for i = 1 to A.length - 1 
        for j = A.length downto i + 1 
            if A[j] < A[j - 1]
                exchange A[j] with A[j - 1]
1
2
3
4
5

a. Let $A^{\prime }$ denote the output of $\text{BUBBLESORT}(A)$ To prove that $\text{BUBBLESORT}$ is correct, we need to prove that it terminates and that

$$A^{\prime }[1]\le A^{\prime }[2]\le \cdots \le A^{\prime }[n],\text{\hspace{1em}(2.3)}$$

where $n=A.length$. In order to show that BUBBLESORT actually sorts, what else do we need to prove?

The next two parts will prove inequality $\text{(2.3)}$.

b. State precisely a loop invariant for the for loop in lines 2–4, and prove that this loop invariant holds. Your proof should use the structure of the loop invariant proof presented in this chapter.

c. Using the termination condition of the loop invariant proved in part (b), state a loop invariant for the for loop in lines 1–4 that will allow you to prove inequality $\text{(2.3)}$. Your proof should use the structure of the loop invariant proof presented in this chapter.

d. What is the worst-case running time of bubblesort? How does it compare to the running time of insertion sort?

a. We need to show that the elements of $A^{\prime }$ form a permutation of the elements of $A$.

b. Loop invariant: At the start of each iteration of the for loop of lines 2–4, $$\begin{gathered} A[j]=\min \\ A[k]:j\le k\le n \end{gathered}$$ and the subarray $A[j..n]$ is a permutation of the values that were in $A[j..n]$ at the time that the loop started.

Initialization: Initially, $j=n$, and the subarray $A[j..n]$ consists of single element $A[n]$. The loop invariant trivially holds.

Maintenance: Consider an iteration for a given value of $j$. By the loop invariant, $A[j]$ is the smallest value in $A[j..n]$. Lines 3–4 exchange $A[j]$ and $A[j-1]$ if $A[j]$ is less than $A[j-1]$, and so $A[j-1]$ will be the smallest value in $A[j-1..n]$ afterward. Since the only change to the subarray $A[j-1..n]$ is this possible exchange, and the subarray $A[j..n]$ is a permutation of the values that were in $A[j..n]$ at the time that the loop started, we see that $A[j-1..n]$ is a permutation of the values that were in $A[j-1..n]$ at the time that the loop started. Decrementing $j$ for the next iteration maintains the invariant.

Termination: The loop terminates when $j$ reaches $i$. By the statement of the loop invariant, $$\begin{gathered} A[i]=\min \\ A[k]:i\le k\le n \end{gathered}$$ and $A[i..n]$ is a permutation of the values that were in $A[i..n]$ at the time that the loop started.

c. Loop invariant: At the start of each iteration of the for loop of lines 1–4, the subarray $A[1..i-1]$ consists of the $i-1$ smallest values originally in $A[1..n]$, in sorted order, and $A[i..n]$ consists of the $n-i+1$ remaining values originally in $A[1..n]$.

Initialization: Before the first iteration of the loop, $i=1$. The subarray $A[1..i-1]$ is empty, and so the loop invariant vacuously holds.

Maintenance: Consider an iteration for a given value of $i$. By the loop invariant, $A[1..i-1]$ consists of the $i$ smallest values in $A[1..n]$, in sorted order. Part (b) showed that after executing the for loop of lines 2–4, $A[i]$ is the smallest value in $A[i..n]$, and so $A[1..i]$ is now the $i$ smallest values originally in $A[1..n]$, in sorted order. Moreover, since the for loop of lines 2–4 permutes $A[i..n]$, the subarray $A[i+1..n]$ consists of the $n-i$ remaining values originally in $A[1..n]$.

Termination: The for loop of lines 1–4 terminates when $i=n$, so that $i-1=n-1$. By the statement of the loop invariant, $A[1..i-1]$ is the subarray $A[1..n-1]$, and it consists of the $n-1$ smallest values originally in $A[1..n]$, in sorted order. The remaining element must be the largest value in $A[1..n]$, and it is in $A[n]$. Therefore, the entire array $A[1..n]$ is sorted.

Note: Tn the second edition, the for loop of lines 1–4 had an upper bound of $A.length$. The last iteration of the outer for loop would then result in no iterations of the inner for loop of lines 1–4, but the termination argument would simplify: $A[1..i-1]$ would be the entire array $A[1..n]$, which, by the loop invariant, is sorted.

d. The running time depends on the number of iterations of the for loop of lines 2–4. For a given value of $i$, this loop makes $n-i$ iterations, and $i$ takes on the values $1,2,\dots ,n-1$. The total number of iterations, therefore, is

$$\begin{align} \sum_{i = 1}^{n - 1} (n - i) & = \sum_{i = 1}^{n - 1} n - \sum_{i = 1}^{n - 1} i \\ & = n(n - 1) - \frac{n(n - 1)}{2} \\ & = \frac{n(n - 1)}{2} \\ & = \frac{n^2}{2} - \frac{n}{2}. \end{align}$$

Thus, the running time of bubblesort is $\Theta (n^2)$ in all cases. The worst-case running time is the same as that of insertion sort.

2-3

The following code fragment implements Horner’s rule for evaluating a polynomial

$$\begin{align} P(x) & = \sum_{k = 0}^n a_k x^k \\ & = a_0 + x(a_1 + x (a_2 + \cdots + x(a_{n - 1} + x a_n) \cdots)), \end{align}$$

given the coefficients $a_0,a_1,\dots ,a_n$ and a value of $x$:

y = 0
for i = n downto 0
    y = a[i] + x * y
1
2
3

a. In terms of $\Theta$-notation, what is the running time of this code fragment for Horner’s rule?

b. Write pseudocode to implement the naive polynomial-evaluation algorithm that computes each term of the polynomial from scratch. What is the running time of this algorithm? How does it compare to Horner’s rule

c. Consider the following loop invariant: At the start of each iteration of the for loop of lines 2-3,

$$y=\sum _{k=0}^{n-(i+1)}{a}_{k+i+1}{x}^k.$$

Interpret a summation with no terms as equaling $0$. Following the structure of the loop invariant proof presented in this chapter, use this loop invariant to show that, at termination, $y={\sum }_{k=0}^n{a}_k{x}^k$.

d. Conclude by arguing that the given code fragment correctly evaluates a polynomial characterized by the coefficients $a_0,a_1,\dots ,a_n$.

a. $\Theta (n)$.

b.

NAIVE-HORNER()
    y = 0
    for k = 0 to n
        temp = 1
        for i = 1 to k
            temp = temp * x
            y = y + a[i] * m
1
2
3
4
5
6
7

The running time is $\Theta (n^2)$, because of the nested loop. It is obviously slower.

c. Initialization: It is pretty trivial, since the summation has no terms which implies $y=0$.

Maintenance: By using the loop invariant, in the end of the $i$-the iteration, we have

$$\begin{align} y & = a_i + x \sum_{k = 0}^{n - (i + 1)} a_{k + i + 1} x^k \\ & = a_i x^0 + \sum_{k = 0}^{n - i - 1} a_{k + i + 1} x^{k + 1} \\ & = a_i x^0 \sum_{k = 1}^{n - i} a_{k + i} x^k \\ & = \sum_{k = 0}^{n - i} a_{k + i} x^k. \end{align}$$

Termination: The loop terminates at $i=-1$. If we substitute,

$$y=\sum _{k=0}^{n-i-1}{a}_{k+i+1}{x}^k=\sum _{k=0}^n{a}_k{x}^k.$$

d. The invariant of the loop is a sum that equals a polynomial with the given coefficients.

2-4

Let $A[1..n]$ be an array of $n$ distinct numbers. If $i<j$ and $A[i]>A[j]$, then the pair $(i,j)$ is called an inversion of $A$.

a. List the five inversions in the array $⟨2,3,8,6,1⟩$.

b. What array with elements from the set $1,2,\dots ,n$ has the most inversions? How many does it have?

c. What is the relationship between the running time of insertion sort and the number of inversions in the input array? Justify your answer.

d. Give an algorithm that determines the number of inversions in any permutation of $n$ elements in $\Theta (n\lg n)$ worst-case time. ($\text{Hint:}$ Modify merge sort).

a. The inversions are $(1,5)$, $(2,5)$, $(3,4)$, $(3,5)$, $(4,5)$. (Remember that inversions are specified by indices rather than by the values in the array.)

b. The array with elements from $1,2,\dots ,n$ with the most inversions is $⟨n,n-1,n-2,\dots ,2,1⟩$. For all $1\le i<j\le n$, there is an inversion $(i,j)$. The number of such inversions is $\left(\genfrac{}{}{0ex}{}{n}{2}\right)=n(n-1)/2$.

c. Suppose that the array $A$ starts out with an inversion $(k,j)$. Then $k<j$ and $A[k]>A[j]$. At the time that the outer for loop of lines 1–8 sets $key=A[j]$, the value that started in $A[k]$ is still somewhere to the left of $A[j]$. That is, it’s in $A[i]$, where $1\le i<j$, and so the inversion has become $(i,j)$. Some iteration of the while loop of lines 5–7 moves $A[i]$ one position to the right. Line 8 will eventually drop $key$ to the left of this element, thus eliminating the inversion. Because line 5 moves only elements that are greater than $key$, it moves only elements that correspond to inversions. In other words, each iteration of the while loop of lines 5–7 corresponds to the elimination of one inversion.

d. We follow the hint and modify merge sort to count the number of inversions in $\Theta (n\lg n)$ time.

To start, let us define a merge-inversion as a situation within the execution of merge sort in which the $\text{MERGE}$ procedure, after copying $A[p..q]$ to $L$ and $A[q+1..r]$ to $R$, has values $x$ in $L$ and $y$ in $R$ such that $x>y$. Consider an inversion $(i,j)$, and let $x=A[i]$ and $y=A[j]$ , so that $i<j$ and $x>y$. We claim that if we were to run merge sort, there would be exactly one mergeinversion involving $x$ and $y$. To see why, observe that the only way in which array elements change their positions is within the $\text{MERGE}$ procedure. Moreover, since $\text{MERGE}$ keeps elements within $L$ in the same relative order to each other, and correspondingly for $R$, the only way in which two elements can change their ordering relative to each other is for the greater one to appear in $L$ and the lesser one to appear in $R$. Thus, there is at least one merge-inversion involving $x$ and $y$. To see that there is exactly one such merge-inversion, observe that after any call of $\text{MERGE}$ that involves both $x$ and $y$, they are in the same sorted subarray and will therefore both appear in $L$ or both appear in $R$ in any given call thereafter. Thus, we have proven the claim.

We have shown that every inversion implies one merge-inversion. In fact, the correspondence between inversions and merge-inversions is one-to-one. Suppose we have a merge-inversion involving values $x$ and $y$, where $x$ originally was $A[i]$ and $y$ was originally $A[j]$. Since we have a merge-inversion, $x>y$. And since $x$ is in $L$ and $y$ is in $R$, $x$ must be within a subarray preceding the subarray containing $y$. Therefore $x$ started out in a position $i$ preceding $y$'s original position $j$, and so $(i,j)$ is an inversion.

Having shown a one-to-one correspondence between inversions and mergeinversions, it suffices for us to count merge-inversions.

Consider a merge-inversion involving $y$ in $R$. Let $z$ be the smallest value in $L$ that is greater than $y$. At some point during the merging process, $z$ and $y$ will be the “exposed” values in $L$ and $R$, i.e., we will have $z=L[i]$ and $y=R[j]$ in line 13 of $\text{MERGE}$. At that time, there will be merge-inversions involving $y$ and $L[i],L[i+1],L[i+2],\dots ,L[n_1]$, and these $n_1-i+1$ merge-inversions will be the only ones involving $y$. Therefore, we need to detect the first time that $z$ and $y$ become exposed during the $\text{MERGE}$ procedure and add the value of $n_1-i+1$ at that time to our total count of merge-inversions.

The following pseudocode, modeled on merge sort, works as we have just described. It also sorts the array $A$.

COUNT-INVERSIONS(A, p, r)
    inversions = 0
    if p < r
        q = floor((p + r) / 2)
        inversions = inversions + COUNT-INVERSIONS(A, p, q)
        inversions = inversions + COUNT-INVERSIONS(A, q + 1, r)
        inversions = inversions + MERGE-INVERSIONS(A, p, q, r)
    return inversions
1
2
3
4
5
6
7
8

MERGE-INVERSIONS(A, p, q, r)
    n[1] = q - p + 1
    n[2] = r - q
    let L[1..n[1] + 1] and R[1..n[2] + 1] be new arrays
    for i = 1 to n[1]
        L[i] = A[p + i - 1]
    for j = 1 to n[2]
        R[j] = A[q + j]
    L[n[1] + 1] = ∞
    L[n[2] + 1] = ∞
    i = 1
    j = 1
    inversions = 0
    for k = p to r
        if R[j] < L[i]
            inversions = inversions + n[1] - i + 1
            A[k] = R[j]
            j = j + 1
        else A[k] = L[i]
            i = i + 1
    return inversions
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

The initial call is $\text{COUNT-INVERSIONS}(A,1,n)$.

In $\text{MERGE-INVERSIONS}$, whenever $R[j]$ is exposed and a value greater than $R[j]$ becomes exposed in the $L$ array, we increase inersions by the number of remaining elements in $L$. Then because $R[j+1]$ becomes exposed, $R[j]$ can never be exposed again. We don’t have to worry about merge-inversions involving the sentinel $\infty$ in $R$, since no value in $L$ will be greater than $\infty$.

Since we have added only a constant amount of additional work to each procedure call and to each iteration of the last for loop of the merging procedure, the total running time of the above pseudocode is the same as for merge sort: $\Theta (n\lg n)$.

2.1-1

Using Figure 2.2 as a model, illustrate the operation of $\text{INSERTION-SORT}$ on the array $A=⟨31,41,59,26,41,58⟩$.

$$\begin{align} A & = \langle 31, 41, 59, 26, 41, 58 \rangle \\ A & = \langle 31, 41, 59, 26, 41, 58 \rangle \\ A & = \langle 31, 41, 59, 26, 41, 58 \rangle \\ A & = \langle 26, 31, 41, 59, 41, 58 \rangle \\ A & = \langle 26, 31, 41, 41, 59, 58 \rangle \\ A & = \langle 26, 31, 41, 41, 58, 59 \rangle \end{align}$$

2.1-2

Rewrite the $\text{INSERTION-SORT}$ procedure to sort into nonincreasing instead of nondecreasing order.

INSERTION-SORT(A) 
    for j = 2 to A.length
        key = A[j]
        i = j - 1
        while i > 0 and A[i] < key
            A[i + 1] = A[i]
            i = i - 1
        A[i + 1] = key
1
2
3
4
5
6
7
8

2.1-3

Consider the searching problem:

Input: A sequence of $n$ numbers $A=⟨a_1,a_2,\dots ,a_n⟩$ and a value $v$.

Output: An index $i$ such that $v=A[i]$ or the special value $\text{NIL}$ if $v$ does not appear in $A$.

Write pseudocode for linear search, which scans through the sequence, looking for $v$. Using a loop invariant, prove that your algorithm is correct. Make sure that your loop invariant fulfills the three necessary properties.

LINEAR-SEARCH(A, v)
    for i = 1 to A.length
       if A[i] == v
            return i
    return NIL
1
2
3
4
5

Loop invariant: At the start of each iteration of the for loop, the subarray $A[1..i-1]$ consists of elements that are different than $v$.

Initialization: Initially the subarray is the empty array, so the prove is trivial.

Maintenance: On each step, we know that $A[1..i-1]$ does not contain $v$. We compare it with $A[i]$. If they are the same, we return $i$, which is a correct result. Otherwise, we continue to the next step. We have already insured that $A[1..i-1]$ does not contain $v$ and that $A[i]$ is different from $v$, so this step preserves the invariant.

Termination: The loop terminates when $i>A.length$. Since $i$ increases by $1$ and $i>A.length$, we know that all the elements in $A$ have been checked and it has been found that $v$ is not among them. Thus, we return $\text{NIL}$.

2.1-4

Consider the problem of adding two $n$-bit binary integers, stored in two $n$-element arrays $A$ and $B$. The sum of the two integers should be stored in binary form in an $(n+1)$-element array $C$. State the problem formally and write pseudocode for adding the two integers.

Input: An array of booleans $A=⟨a_1,a_2,\dots ,a_n⟩$ and an array of booleans $B=⟨b_1,b_2,\dots ,b_n⟩$, each representing an integer stored in binary format (each digit is a number, either $0$ or $1$, least-significant digit first) and each of length $n$.

Output: An array $C=⟨c_1,c_2,\dots ,c_{n+1}⟩$ such that $C^{\prime }=A^{\prime }+B^{\prime }$ where $A^{\prime }$, $B^{\prime }$ and $C^{\prime }$ are the integers, represented by $A$, $B$ and $C$.

ADD-BINARY(A, B)
    C = new integer[A.length + 1]
    carry = 0
    for i = 1 to A.length
        C[i] = (A[i] + B[i] + carry) % 2  // remainder
        carry = (A[i] + B[i] + carry) / 2 // quotient
    C[i] = carry
    return C
1
2
3
4
5
6
7
8

2.2-1

Express the function $n^3/1000-100n^2-100n+3n$ in terms of $\Theta$-notation.

$\Theta (n^3)$.

2.2-2

Consider sorting $n$ numbers stored in array $A$ by first finding the smallest element of $A$ and exchanging it with the element in $A[1]$. Then find the second smallest element of $A$, and exchange it with $A[2]$. Continue in this manner for the first $n-1$ elements of $A$. Write pseudocode for this algorithm, which is known as selection sort. What loop invariant does this algorithm maintain? Why does it need to run for only the first $n-1$ elements, rather than for all $n$ elements? Give the best-case and worst-case running times of selection sort in $\Theta$-notation.

SELECTION-SORT(A)
    n = A.length
    for j = 1 to n - 1
        smallest = j
        for i = j + 1 to n
            if A[i] < A[smallest]
                smallest = i
        exchange A[j] with A[smallest]
1
2
3
4
5
6
7
8

The algorithm maintains the loop invariant that at the start of each iteration of the outer for loop, the subarray $A[1..j-1]$ consists of the $j-1$ smallest elements in the array $A[1..n]$, and this subarray is in sorted order. After the first $n-1$ elements, the subarray $A[1..n]$ contains the smallest $n-1$ elements, sorted, and therefore element $A[n]$ must be the largest element.

The running time of the algorithm is $\Theta (n^2)$ for all cases.

2.2-3

Consider linear search again (see Exercise 2.1-3). How many elements of the in- put sequence need to be checked on the average, assuming that the element being searched for is equally likely to be any element in the array? How about in the worst case? What are the average-case and worst-case running times of linear search in $\Theta$-notation? Justify your answers.

If the element is present in the sequence, half of the elements are likely to be checked before it is found in the average case. In the worst case, all of them will be checked. That is, $n/2$ checks for the average case and $n$ for the worst case. Both of them are $\Theta (n)$.

2.2-4

How can we modify almost any algorithm to have a good best-case running time?

Modify the algorithm so it tests whether the input satisfies some special-case condition and, if it does, output a pre-computed answer. The best-case running time is generally not a good measure of an algorithm.

2.3-1

Using Figure 2.4 as a model, illustrate the operation of merge sort on the array $A=⟨3,41,52,26,38,57,9,49⟩$.

$$[3][41][52][26][38][57][9][49]$$

$$\downarrow$$

$$[3|41][26|52][38|57][9|49]$$

$$\downarrow$$

$$[3|26|41|52][9|38|49|57]$$

$$\downarrow$$

$$[3|9|26|38|41|49|52|57]$$

2.3-2

Rewrite the $\text{MERGE}$ procedure so that it does not use sentinels, instead stopping once either array $L$ or $R$ has had all its elements copied back to $A$ and then copying the remainder of the other array back into $A$.

MERGE(A, p, q, r)
    n[1] = q - p + 1
    n[2] = r - q
    let L[1..n[1]] and R[1..n[2]] be new arrays
    for i = 1 to n[1]
        L[i] = A[p + i - 1]
    for j = 1 to n[2]
        R[j] = A[q + j]
    i = 1
    j = 1
    for k = p to r
        if i > n[1]
            A[k] = R[j]
            j = j + 1
        else if j > n[2]
            A[k] = L[i]
            i = i + 1
        else if L[i] ≤ R[j]
            A[k] = L[i]
            i = i + 1
        else
            A[k] = R[j]
            j = j + 1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

2.3-3

Use mathematical induction to show that when $n$ is an exact power of $2$, the solution of the recurrence

T ( n ) = { 2 if  n = 2 , 2 T ( n / 2 ) if  n = 2 k , for  k &gt; 1 T(n) =

$$\begin{cases} 2 &amp; \text{if } n = 2, \\\\ 2T(n / 2) &amp; \text{if } n = 2^k, \text{for } k &gt; 1 \end{cases}$$ T(n)=⎩⎪⎨⎪⎧​22T(n/2)​if n=2,if n=2k,for k>1​

is $T(n)=n\lg n$.

The base case is when $n=2$, and we have $n\lg n=2\lg 2=2\cdot 1=2$.

For the inductive step, our inductive hypothesis is that $T(n/2)=(n/2)\lg (n/2)$. Then

$$\begin{align} T(n) & = 2T(n / 2) + n \\ & = 2(n / 2) \lg(n / 2) + n \\ & = n(\lg n - 1) + n \\ & = n\lg n - n + n \\ & = n\lg n, \end{align}$$

which completes the inductive proof for exact powers of $2$.

2.3-4

We can express insertion sort as a recursive procedure as follows. In order to sort $A[1..n]$, we recursively sort $A[1..n-1]$ and then insert $A[n]$ into the sorted array $A[1..n-1]$. Write a recurrence for the running time of this recursive version of insertion sort.

Since it takes $\Theta (n)$ time in the worst case to insert $A[n]$ into the sorted array $A[1..n-1]$, we get the recurrence

T ( n ) = { Θ ( 1 ) if  n = 1 , T ( n − 1 ) + Θ ( n ) if  n &gt; 1. T(n) =

$$\begin{cases} \Theta(1) &amp; \text{if } n = 1, \\\\ T(n - 1) + \Theta(n) &amp; \text{if } n &gt; 1. \end{cases}$$ T(n)=⎩⎪⎨⎪⎧​Θ(1)T(n−1)+Θ(n)​if n=1,if n>1.​

Although the exercise does not ask you to solve this recurrence, its solution is $T(n)=\Theta (n^2)$.

2.3-5

Referring back to the searching problem (see Exercise 2.1-3), observe that if the sequence $A$ is sorted, we can check the midpoint of the sequence against $v$ and eliminate half of the sequence from further consideration. The binary search algorithm repeats this procedure, halving the size of the remaining portion of the sequence each time. Write pseudocode, either iterative or recursive, for binary search. Argue that the worst-case running time of binary search is $\Theta (\lg n)$.

Procedure $\text{BINARY-SEARCH}$ takes a sorted array $A$, a value $v$, and a range $[low..high]$ of the array, in which we search for the value $v$. The procedure compares to the array entry at the midpoint of the range and decides to eliminate half the range from further consideration. We give both iterative and recursive versions, each of which returns either an index $i$ such that $A[i]=v$, or $\text{NIL}$ if no entry of $A[low..high]$ contains the value $v$. The initial call to either version should have the parameters $A$, $v$, $1$, $n$.

ITERATIVE-BINARY-SEARCH(A, v, low, high)
    while low ≤ high
        mid = floor((low + high) / 2)
        if v == A[mid]
            return mid
        else if v > A[mid]
            low = mid + 1
        else high = mid - 1
    return NIL
1
2
3
4
5
6
7
8
9

RECURSIVE-BINARY-SEARCH(A, v, low, high)
    if low > high
        return NIL
    mid = floor((low + high) / 2)
    if v == A[mid]
        return mid
    else if v > A[mid]
        return RECURSIVE-BINARY-SEARCH(A, v, mid + 1, high)
    else return RECURSIVE-BINARY-SEARCH(A, v, low, mid - 1)
1
2
3
4
5
6
7
8
9

Both procedures terminate the search unsuccessfully when the range is empty (i.e., $low>high$) and terminate it successfully if the value $v$ has been found. Based on the comparison of $v$ to the middle element in the searched range, the search continues with the range halved. The recurrence for these procedures is therefore $T(n)=T(n/2)+\Theta (1)$, whose solution is $T(n)=\Theta (\lg n)$.

2.3-6

Observe that the while loop of lines 5–7 of the $\text{INSERTION-SORT}$ procedure in Section 2.1 uses a linear search to scan (backward) through the sorted subarray $A[i..j-1]$. Can we use a binary search (see Exercise 2.3-5) instead to improve the overall worst-case running time of insertion sort to $\Theta (n\lg n)$?

The while loop of lines 5–7 of procedure $\text{INSERTION-SORT}$ scans backward through the sorted array $A[1..j-1]$ to find the appropriate place for $A[j]$. The hitch is that the loop not only searches for the proper place for $A[j]$, but that it also moves each of the array elements that are bigger than $A[j]$ one position to the right (line 6). These movements can take as much as $\Theta (j)$ time, which occurs when all the $j-1$ elements preceding $A[j]$ are larger than $A[j]$. We can use binary search to improve the running time of the search to $\Theta (\lg j)$, but binary search will have no effect on the running time of moving the elements. Therefore, binary search alone cannot improve the worst-case running time of $\text{INSERTION-SORT}$ to $\Theta (n\lg n)$.

2.3-7 $\star$

Describe a $\Theta (n\lg n)$-time algorithm that, given a set $S$ of $n$ integers and another integer $x$, determines whether or not there exist two elements in $S$ whose sum is exactly $x$.

The following algorithm solves the problem:

1. Sort the elements in $S$.
2. Form the set KaTeX parse error: Expected '}', got 'EOF' at end of input: …\\{z: z = x - y for some KaTeX parse error: Expected 'EOF', got '}' at position 10: y \in S\\}̲.
3. Sort the elements in $S^{\prime }$.
4. Merge the two sorted sets $S$ and $S^{\prime }$.
5. There exist two elements in $S$ whose sum is exactly $x$ if and only if the same value appears in consecutive positions in the merged output.

To justify the claim in step 4, first observe that if any value appears twice in the merged output, it must appear in consecutive positions. Thus, we can restate the condition in step 5 as there exist two elements in $S$ whose sum is exactly $x$ if and only if the same value appears twice in the merged output.

Suppose that some value $w$ appears twice. Then $w$ appeared once in $S$ and once in $S^{\prime }$. Because $w$ appeared in $S^{\prime }$, there exists some $y\in S$ such that $w=x-y$, or $x=w+y$. Since $w\in S$, the elements $w$ and $y$ are in $S$ and sum to $x$.

Conversely, suppose that there are values $w,y\in S$ such that $w+y=x$. Then, since $x-y=w$, the value $w$ appears in $S^{\prime }$. Thus, $w$ is in both $S$ and $S^{\prime }$, and so it will appear twice in the merged output.

Steps 1 and 3 require $\Theta (n\lg n)$ steps. Steps 2, 4, 5, and 6 require $O(n)$ steps. Thus the overall running time is $O(n\lg n)$.

A reader submitted a simpler solution that also runs in $\Theta (n\lg n)$ time. First, sort the elements in $S$, taking $\Theta (n\lg n)$ time. Then, for each element $y$ in $S$, perform a binary search in $S$ for $x-y$. Each binary search takes $O(\lg n)$ time, and there are are most $n$ of them, and so the time for all the binary searches is $O(n\lg n)$. The overall running time is $\Theta (n\lg n)$.

Another reader pointed out that since $S$ is a set, if the value $x/2$ appears in $S$, it appears in $S$ just once, and so $x/2$ cannot be a solution.

3.1-1

Let $f(n)+g(n)$ be asymptotically nonnegative functions. Using the basic definition of $\Theta$-notation, prove that $\max (f(n),g(n))=\Theta (f(n)+g(n))$.

First, let’s clarify what the function $\max (f(n),g(n))$ is. Let’s define the function $h(n)=\max (f(n),g(n))$. Then

h ( n ) = { f ( n )  if  f ( n ) ≥ g ( n ) , g ( n )  if  f ( n ) &lt; g ( n ) . h(n) =

$$\begin{cases} f(n) &amp; \text{ if } f(n) \ge g(n), \\\\ g(n) &amp; \text{ if } f(n) &lt; g(n). \end{cases}$$ h(n)=⎩⎪⎨⎪⎧​f(n)g(n)​ if f(n)≥g(n), if f(n)<g(n).​

Since $f(n)$ and $g(n)$ are asymptotically nonnegative, there exists $n_0$ such that $f(n)\ge 0$ and $g(n)\ge 0$ for all $n\ge n_0$. Thus for $n\ge n_0$ , $f(n)+g(n)\ge f(n)\ge 0$ and $f(n)+g(n)\ge g(n)\ge 0$. Since for any particular $n$, $h(n)$ is either $f(n)$ or $g(n)$, we have $f(n)+g(n)\ge h(n)\ge 0$, which shows that

$$h(n)=\max (f(n),g(n))\le c_2(f(n)+g(n))$$

for all $n\ge n_0$ (with $c_2=1$ in the definition of $\Theta$).

Similarly, since for any particular $n$, $h(n)$ is the larger of $f(n)$ and $g(n)$, we have for all $n\ge n_0$, $0\le f(n)\le h(n)$ and $0\le g(n)\le h(n)$. Adding these two inequalities yields $0\le f(n)+g(n)\le 2h(n)$, or equivalently $0\le (f(n)+g(n))/2\le h(n)$, which shows that

$$h(n)=\max (f(n),g(n))\ge c_1(f(n)+g(n))$$

for all $n\ge n_0$ (with $c_1=1/2$ in the definition of $\Theta$).

3.1-2

Show that for any real constants $a$ and $b$, where $b>0$,

$$(n+a{)}^b=\Theta (n^b).\text{\hspace{1em}(3.2)}$$

To show that $(n+a{)}^b=\Theta (n^b)$, we want to find constants $c_1,c_2,n_0>0$ such that $0\le c_1{n}^b\le (n+a{)}^b\le c_2{n}^b$ for all $n\ge n_0$.

Note that

$$\begin{align} n + a & \le n + |a| & \\ & \le 2n & \text{ when } |a| \le n, \end{align}$$

and

$$\begin{align} n + a & \ge n - |a| & \\ & \ge \frac{1}{2}n & \text{ when } |a| \le \frac{1}{2}n. \end{align}$$

Thus, when $n\ge 2|a|$,

$$0\le \frac{1}{2}n\le n+a\le 2n.$$

Since $b>0$, the inequality still holds when all parts are raised to the power $b$:

$$\begin{align} 0 \le \Big(\frac{1}{2}n\Big)^b & \le (n + a)^b \le (2n)^b, \\ 0 \le \Big(\frac{1}{2}\Big)^b n^b & \le (n + a)^b \le 2^b n^b. \end{align}$$

Thus, $c_1=(1/2{)}^b$, $c_2=2^b$, and $n_0=2|a|$ satisfy the definition.

3.1-3

Explain why the statement, ‘‘The running time of algorithm $A$ is at least $O(n^2)$,’’ is meaningless.

Let the running time be $T(n)$. $T(n)\ge O(n^2)$ means that $T(n)\ge f(n)$ for some function $f(n)$ in the set $O(n^2)$. This statement holds for any running time $T(n)$, since the function $g(n)=0$ for all $n$ is in $O(n^2)$, and running times are always nonnegative. Thus, the statement tells us nothing about the running time.

3.1-4

Is $2^{n+1}=O(2^n)$? Is $2^{2n}=O(2^n)$?

$2^{n+1}=O(2^n)$, but $2^{2n}̸=O(2^n)$.

• To show that $2^{n+1}=O(2^n)$, we must find constants $c$; $n_0>0$ such that

  $$0\le 2^{n+1}\le c\cdot 2^n\text{ for all }n\ge n_0.$$

  Since $2^{n+1}=2\cdot 2^n$ for all $n$, we can satisfy the definition with $c=2$ and $n_0=1$.

• To show that $2^{2n}̸=O(2^n)$, assume there exist constants $c,n_0>0$ such that

  $$0\le 2^{2n}\le c\cdot 2^n\text{ for all }n\ge n_0.$$

  Then $2^{2n}=2^n\cdot 2^n\le c\cdot 2^n\Rightarrow 2^n\le c$. But no constant is greater than all $2^n$, and so the assumption leads to a contradiction.

3.1-5

Prove Theorem 3.1.

The theorem states:

For any two functions $f(n)$ and $g(n)$, we have $f(n)=\Theta (g(n))$ if and only if $f(n)=O(g(n))$ and $f(n)=\Omega (g(n))$.

From $f=\Theta (g(n))$, we have that

$$0\le c_{1}g(n)\le f(n)\le c_{2}g(n)\text{ for }n>n_0.$$

We can pick the constants from here and use them in the definitions of $O$ and $\Omega$ to show that both hold.

From $f(n)=\Omega (g(n))$ and $f(n)=O(g(n))$, we have that

$$\begin{align} & 0 \le c_3g(n) \le f(n) & \text{ for all } n \ge n_1 \\ \text{and } & 0 \le f(n) \le c_4g(n) & \text{ for all } n \ge n_2. \end{align}$$

If we let $n_3=\max (n_1,n_2)$ and merge the inequalities, we get

$$0\le c_{3}g(n)\le f(n)\le c_{4}g(n)\text{ for all }n>n_3.$$

Which is the definition of $\Theta$.

3.1-6

Prove that the running time of an algorithm is $\Theta (g(n))$ if and only if its worst-case running time is $O(g(n))$ and its best-case running time is $\Omega (g(n))$.

If $T_w$ is the worst-case running time and $T_b$ is the best-case running time, we know that

$$\begin{align} & 0 \le c_1g(n) \le T_b(n) & \text{ for } n > n_b \\ \text{and } & 0 \le T_w(n) \le c_2g(n) & \text{ for } n > n_w. \end{align}$$

Combining them we get

$$0\le c_{1}g(n)\le T_b(n)\le T_w(n)\le c_{2}g(n)\text{ for }n>\max (n_b,n_w).$$

Since the running time is bound between $T_b$ and $T_w$ and the above is the definition of the $\Theta$-notation, proved.

3.1-7

Prove $o(g(n))\cap w(g(n))$ is the empty set.

We know that for any $c>0$,

$$\begin{align} & \exists n_1 > 0: 0 \le f(n) < cg(n) \\ \text{and } & \exists n_2 > 0: 0 \le cg(n) < f(n). \end{align}$$

If we pick $n_0=\max (n_1,n_2)$, from the problem definition we get

$$f(n)<cg(n)<f(n).$$

There is no solutions, which means that the intersection is the empty set.

3.1-8

We can extend our notation to the case of two parameters $n$ and $m$ that can go to infinity independently at different rates. For a given function $g(n,m)$ we denote $O(g(n,m))$ the set of functions:

$$\begin{align} O(g(n, m)) = \{f(n, m): & \text{ there exist positive constants } c, n_0, \text{ and } m_0 \\ & \text{ such that } 0 \le f(n, m) \le cg(n, m) \\ & \text{ for all } n \ge n_0 \text{ or } m \ge m_0.\} \end{align}$$

Give corresponding definitions for $\Omega (g(n,m))$ and $\Theta (g(n,m))$.

$$\begin{align} \Omega(g(n, m)) = \{f(n, m): & \text{ there exist positive constants } c, n_0, \text{ and } m_0 \\ & \text{ such that } 0 \le cg(n, m) \le f(n, m) \\ & \text{ for all } n \ge n_0 \text{ or } m \ge m_0.\} \end{align}$$

$$\begin{align} \Theta(g(n, m)) = \{f(n, m): & \text{ there exist positive constants } c_1, c_2, n_0, \text{ and } m_0 \\ & \text{ such that } 0 \le c_1 g(n, m) \le f(n, m) \le c_2 g(n, m) \\ & \text{ for all } n \ge n_0 \text{ or } m \ge m_0.\} \end{align}$$

3.2-1

Show that if $f(n)$ and $g(n)$ are monotonically increasing functions, then so are the functions $f(n)+g(n)$ and $f(g(n))$, and if $f(n)$ and $g(n)$ are in addition nonnegative, then $f(n)\cdot g(n)$ is monotonically increasing.

$$\begin{align} f(m) \le f(n) \quad \text{ for } m \le n \\ g(m) \le g(n) \quad \text{ for } m \le n, \\ \to f(m) + g(m) \le f(n) + g(n), \end{align}$$

which proves the first function.

Then

$$f(g(m))\le f(g(n))\text{ for }m\le n.$$

This is true, since $g(m)>g(n)$ and $f(n)$ is monotonically increasing.

If both functions are nonnegative, then we can multiply the two equalities and we get

$$f(m)\cdot g(m)\le f(n)\cdot g(n).$$

3.2-2

Prove equation $\text{(3.16)}$.

$$\begin{align} a^{\log_b c} = a^\frac{\log_a c}{\log_a b} = (a^{\log_a c})^{\frac{1}{\log_a b}} = c^{\log_b a} \end{align}$$

3.2-3

Prove equation $\text{(3.19)}$. Also prove that $n̸=\omega (2^n)$ and $n̸=o(n^n)$.

$$\lg (n!)=\Theta (n\lg n)\text{\hspace{1em}(3.19)}$$

We use Stirling’s approximation:

$$\begin{align} \lg(n!) & = \lg\Bigg(\sqrt{2\pi n}\Big(\frac{n}{e}\Big)^n\Big(1 + \Theta(\frac{1}{n})\Big)\Bigg) \\ & = \lg\sqrt{2\pi n } + \lg\Big(\frac{n}{e}\Big)^n + \lg\Big(1+\Theta(\frac{1}{n})\Big) \\ & = \Theta(\sqrt n) + n\lg{\frac{n}{e}} + \lg\Big(\Theta(1) + \Theta(\frac{1}{n})\Big) \\ & = \Theta(\sqrt n) + \Theta(n\lg n) + \Theta(\frac{1}{n}) \\ & = \Theta(n\lg n). \end{align}$$

The other two are

$$\forall n>3:2^n=\underset{\text{n times}}{\underbrace{2\cdot 2\cdot \cdots \cdot 2}}<1\cdot 2\cdot \cdots \cdot n=n!\Rightarrow n!=\omega (2^n).$$

and

$$\forall n>1:n!=1\cdot 2\cdot \cdots n<\underset{\text{n times}}{\underbrace{n\cdot n\cdot \cdots \cdot n}}=n^n\Rightarrow n!=o(n^n).$$

3.2-4 $\star$

Is the function $\lceil \lg n\rceil !$ polynomially bounded? Is the function $\lceil \lg \lg n\rceil !$ polynomially bounded?

$\lceil \lg n\rceil !$ is not polynomially bounded, but $\lceil \lg \lg n\rceil !$ is.

Proving that a function $f(n)$ is polynomially bounded is equivalent to proving that $\lg (f(n))=O(\lg n)$ for the following reasons.

• If $f$ is polynomially bounded, then there exist constants $c$, $k$, $n_0$ such that for all $n\ge n_0$, $f(n)\le c{n}^k$. Hence, $\lg (f(n))\le kc\lg n$, which, since $c$ and $k$ are constants, means that $\lg (f(n))=O(\lg n)$.
• Similarly, if $\lg (f(n)=O(\lg n)$, then $f$ is polynomially bounded.

In the following proofs, we will make use of the following two facts:

1. $\lg (n!)=\Theta (n\lg n)$ (by equation $\text{(3.19)}$).
2. $\lceil \lg n\rceil =\Theta (\lg n)$, because
   • $\lceil \lg n\rceil \ge \lg n$
   • $\lceil \lg n\rceil <\lg n+1\le 2\lg n\text{ for all }n\ge 2$

$$\begin{align} \lg(\lceil \lg n \rceil!) & = \Theta(\lceil \lg n \rceil \lg \lceil \lg n \rceil) \\ & = \Theta(\lg n\lg\lg n) \\ & = \omega(\lg n). \end{align}$$

Therefore, $\lg (\lceil \lg n\rceil !)̸=O(\lg n)$, and so $\lceil \lg n\rceil !$ is not polynomially bounded.

$$\begin{align} \lg(\lceil \lg\lg n \rceil!) & = \Theta(\lceil \lg\lg n \rceil \lg \lceil \lg\lg n \rceil) \\ & = \Theta(\lg\lg n\lg\lg\lg n) \\ & = o((\lg\lg n)^2) \\ & = o(\lg^2(\lg n)) \\ & = o(\lg n). \end{align}$$

3.2-5 $\star$

Which is asymptotically larger: KaTeX parse error: Expected group after '^' at position 8: \lg(\lg^̲\*n) or KaTeX parse error: Expected group after '^' at position 4: \lg^̲\*(\lg n)?

KaTeX parse error: Expected group after '^' at position 4: \lg^̲\*(\lg n) is asymptotically larger because KaTeX parse error: Expected group after '^' at position 4: \lg^̲\*(\lg n) = \lg….

3.2-6

Show that the golden ratio $\varphi$ and its conjugate $\hat{\varphi }$ both satisfy the equation $x^2=x+1$.

$$\begin{align} \phi^2 - \phi - 1 & = \big(\frac{1 + \sqrt 5}{2}\big)^2 - \frac{1 + \sqrt 5}{2} - 1 \\ & = \frac{1 + 2\sqrt 5 + 5 - 2 - 2\sqrt 5 - 4}{4} \\ & = 0. \end{align}$$
$$\begin{align} \hat\phi^2 - \hat\phi - 1 & = \big(\frac{1 - \sqrt 5}{2}\big)^2 - \frac{1 - \sqrt 5}{2} - 1 \\ & = \frac{1 - 2\sqrt 5 + 5 - 2 + 2\sqrt 5 - 4}{4} \\ & = 0. \end{align}$$

3.2-7

Prove by induction that the $i$th Fibonacci number satisfies the equality

$$F_i=\frac{{\varphi }^i-{\hat{\varphi }}^i}{\sqrt{5}},$$

where $\varphi$ is the golden ratio and $\hat{\varphi }$ is its conjugate.

We have two base cases: $i=0$ and $i=1$. For $i=0$, we have

\frac{\phi^0 - \hat\phi^0}{\sqrt 5}
& = \frac{1 - 1}{\sqrt 5} \\
& = 0 \\
& = F_0,

and for $i=1$, we have

$$\begin{align} \frac{\phi^1 - \hat\phi^1}{\sqrt 5} & = \frac{(1 + \sqrt 5) - (1 - \sqrt 5)}{2\sqrt 5} \\ & = \frac{2\sqrt 5}{2\sqrt 5} \\ & = 1 \\ & = F_1. \end{align}$$

For the inductive case, the inductive hypothesis is that $F_{i-1}-({\varphi }^{i-1}-{\hat{\varphi }}^{i-1})/\sqrt{5}$ and $F_{i-2}=({\varphi }^{i-2}-{\hat{\varphi }}^{i-2})/\sqrt{5}$. We have

F_i & = F_{i - 1} + F_{i - 2} & \text{(equation (3.22)} \\
& = \frac{\phi^{i - 1} - \hat\phi^{i - 1}}{\sqrt 5} + \frac{\phi^{i - 2} - \hat\phi^{i - 2}}{\sqrt 5} & \text{(inductive hypothesis)} \\
& = \frac{\phi^{i - 2}(\phi + 1) - \hat\phi^{i - 2}(\hat\phi + 1)}{\sqrt 5} \\
& = \frac{\phi^{i - 2}\phi^2 - \hat\phi^{i - 2}\hat\phi^2}{\sqrt 5} & \text{(Exercise 3.2-6)} \\
& = \frac{\phi^i - \hat\phi^i}{\sqrt 5}.

3.2-8

Show that $k\ln k=\Theta (n)$ implies $k=\Theta (n/\ln n)$.

From the symmetry of $\Theta$,

$$k\ln k=\Theta (n)\Rightarrow n=\Theta (k\ln k).$$

Let’s find $\ln n$,

$$\ln n=\Theta (\ln (k\ln k))=\Theta (\ln k+\ln \ln k)=\Theta (\ln k).$$

Let’s divide the two,

$$\frac{n}{\ln n}=\frac{\Theta (k\ln k)}{\Theta (\ln k)}=\Theta (\frac{k\ln k}{\ln k})=\Theta (k).$$

The last step above follows from the property that any polylogarithmic function grows more slowly than any positive polynomial function, i.e., that for constants $a,b>0$, we have ${\lg }^b=o(n^a)$. Substitute $\lg n$ for $n$, $2$ for $b$, and $1$ for $a$, giving ${\lg }^2(\lg n)=o(\lg n)$.

Therefore, $\lg (\lceil \lg \lg n\rceil !)=O(\lg n)$, and so $\lceil \lg \lg n\rceil !$ is polynomially bounded.

3-1

Let
$$p(n)=\sum _{i=0}^d{a}_i{n}^i,$$

where $a_d>0$, be a degree-$d$ polynomial in $n$, and let $k$ be a constant. Use the definitions of the asymptotic notations to prove the following properties.

a. If $k\ge d$, then $p(n)=O(n^k)$.

b. If $k\le d$, then $p(n)=\Omega (n^k)$.

c. If $k=d$, then $p(n)=\Theta (n^k)$.

d. If $k>d$, then $p(n)=o(n^k)$.

e. If $k<d$, then $p(n)=\omega (n^k)$.

Let’s see that $p(n)=O(n^d)$. We need do pick $c=a_d+b$, such that

$$\sum _{i=0}^d=a_d{n}^d+a_{d-1}{n}^{d-1}+\cdots +a_{1}n+a_0\le c{n}^d.$$

When we divide by $n^d$, we get

$$c=a_d+b\ge a_d+\frac{a_{d-1}}{n}+\frac{a_{d-2}}{n^2}+\cdots +\frac{a_0}{n^d}.$$

and

$$b\ge \frac{a_{d-1}}{n}+\frac{a_{d-2}}{n^2}+\cdots +\frac{a_0}{n^d}.$$

If we choose $b=1$, then we can choose $n_0$,

$$n_0=\max (d{a}_{d-1},d\sqrt{a_{d-2}},\dots ,d\sqrt[d]{a_0}).$$

Now we have $n_0$ and $c$, such that

$$p(n)\le c{n}^d\text{for }n\ge n_0,$$

which is the definition of $O(n^d)$.

By chosing $b=-1$ we can prove the $\Omega (n^d)$ inequality and thus the $\Theta (n^d)$ inequality.

It is very similar to prove the other inequalities.

3-2

Indicate for each pair of expressions $(A,B)$ in the table below, whether $A$ is $O$, $o$, $\Omega$, $\omega$, or $\Theta$ of $B$. Assume that $k\ge 1$, $ϵ>0$, and $c>1$ are constants. Your answer should be in the form of the table with ‘‘yes’’ or ‘‘no’’ written in each box.

$$\begin{array}{ccccccc} A & B & O & o & \Omega & \omega & \Theta \\ \hline \lg^k n & n^\epsilon & yes & yes & no & no & no \\ n^k & c^n & yes & yes & no & no & no \\ \sqrt n & n^{\sin n} & no & no & no & no & no \\ 2^n & 2^{n / 2} & no & no & yes & yes & no \\ n^{\lg c} & c^{\lg n} & yes & no & yes & no & yes \\ \lg(n!) & \lg(n^n) & yes & no & yes & no & yes \end{array}$$