Exercises

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?

Sol’n:

Claim: The solution space is

\[ \{ n : \text{insertion sort beats merge sort} \} = \{2, 3, \dots, 43\}. \]

Proof:

Consider a rewrite of the solution set,

\[\begin{align*} \{ n : \text{insertion sort beats merge sort} \} & = \{ n : 8 n^2 \le 64 n \lg n \} \\ & = \{ n : n \le 8 \lg n \}. \end{align*} \]

Consider the function \(f(x) = x - 8 \ln x\), and that it’s second derivative \(f^{\prime\prime}(x) = 8 / (x^2 \ln 2)\) is everywhere positive, thus \(f\) is concave up everywhere. This together with the following set of test values proves our claim:

\[\begin{align*} f(1) & > 0, \\ f(2) & < 0, \\ f(43) & < 0, \\ f(44) & > 0. \\ \end{align*} \]

We provide the following function to easily check these values.

import math
def f(n):
    return n - 8 * math.log(n, 2)

1.2-3

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

Sol’n

\[\begin{align*} \min \{ n : \text{first algorithm faster than second algorithm} \} & = \min \{ n : 100 n^2 \le 2^n \}. \end{align*} \]

def f(n):
    return 100 * n ** 2 - 2 ** n

i = 0
result = []
while True:
    v = f(i)
    result.append((i, v))
    if v < 0:
        break
    i += 1

print(result)

A quick search shows \(n = 15\).