Problem 1

$(a)$ $n! \leq n^{n}$ for all $n \in Z$ , so $n! = O (n^{n})$ . There does not exist $c > 0$ such that $c n^{n} \leq n!$ for all $n$ greater than some $n_{0}$ , since $n! / n^{n} \to 0$ as $n \to \infty$ , so $n! \neq \in Θ (n^{n})$ .

$(b)$

lo g n! = i = 1 \sum n lo g i \geq i = ⌈ n /2 ⌉ \sum n lo g n /2 = \frac{n}{2} (lo g n - 1)

For $n \geq 4$ , $lo g n \geq 2$ , so $lo g n - 1 \geq \frac{1}{2} lo g n$ . Thus, for $n \geq 4$ ,

lo g n! \geq \frac{1}{4} lo g n .

Since $(1/4) lo g n \leq lo g n! \leq lo g n$ , we have $lo g n! = Θ (lo g n)$ .

$(c)$

\int_{1}^{n} \frac{1}{x} d x \leq i = 1 \sum n \frac{1}{i} \leq 1 + \int_{1}^{n} \frac{1}{x} d x lo g n \leq i = 1 \sum n \frac{1}{i} \leq 1 + lo g n .

For $n \geq 2$ , $1 + lo g n \leq 2 lo g n$ . Thus, $\sum_{i = 1}^{n} 1/ i = Θ (lo g n)$ .

Problem 2

$(a)$

QMedian (A [1.. n], B [1.. n]) : m_{A} \leftarrow Median (A [1.. n]) m_{B} \leftarrow Median (B [1.. n]) if n = 1 : return min (m_{A}, m_{B}) l_{r} \leftarrow ⌈(n + 1) /2 ⌉ l_{l} \leftarrow ⌈ n /2 ⌉ if m_{A} < m_{B} : return QMedian (A [l_{r} .. n], B [1.. l_{l}]) if m_{A} > m_{B} : return QMedian (B [l_{r} .. n], A [1.. l_{l}]) else : return m_{A}

$QMedian$ compares the medians $m_{A}$ and $m_{B}$ of $A$ and $B$ . Denote the result of merging $A$ and $B$ by $A \cup B$ . If $m_{A} = m_{B}$ , it is clear that $m_{A}$ will be the median of $A \cup B$ . Consider the case when $m_{A} < m_{B}$ . Every element in $A [1.. l_{r} - 1]$ has at least $n + 1$ elements in $A \cup B$ that are greater than it, and thus cannot be the median of $A \cup B$ . Symmetrically, no element of $B [l_{l} + 1.. n]$ can be the median of $A \cup B$ . Since the two chunks are of equal size, the median of $A \cup B$ is equal to the median of $A [l_{r} .. n] \cup B [1.. l_{l}]$ .

The recurrence relation for $QMedian$ is given by

T (n) = T (n /2) + O (1) .

Since we are halving the array size at each step, the algorithm will terminate after $lo g n$ recursive calls. At each step of the recursion, we only perform $O (1)$ operations. Therefore, $T (n) = O (lo g n)$ .

$(b)$

The median of an even length array is considered to be its left median. All elements are distinct. We use sentinels $A [0] = - \infty$ and $A [n + 1] = \infty$ for all lists $A [1.. n]$ . Lists constructed with indices out of order (like $A [3..1]$ ) are empty lists. $KSmallest$ is the function from part $(c)$ ; it runs in log time.

QMedian3 (A [1.. a], B [1.. b], C [1.. c]) : m_{A} \leftarrow Median (A [1.. a]) m_{B} \leftarrow Median (B [1.. b]) m_{C} \leftarrow Median (C [1.. c]) if any of A, B, or C are empty : (A^{'}, B^{'}, C^{'}) \leftarrow a permutation of (A, B, C) such that C^{'} is empty return KSmallest (A^{'} [1.. a^{'}], B^{'} [1.. b^{'}], ⌈(a^{'} + b^{'}) /2 ⌉) else : (L, K, G) \leftarrow the permutation of (A, B, C) such that m_{L} < m_{K} < m_{G} α \leftarrow min (⌈ l /2 ⌉, ⌊ g /2 ⌋) if α = 0 : # g=1 if k, l are even and m_{G} < K [k /2 + 1] and m_{G} < L [l /2 + 1] return m_{G} else α \leftarrow 1 return QMedian3 (L [α + 1.. l], K, G [1.. g - α])

Consider lists $L, K, G$ such that $m_{L} < m_{K} < m_{G}$ . I claim that

No element in $L [1.. ⌈ l /2 ⌉]$ can be the median of $A \cup B \cup C$ . Indeed, every element in $L [1.. ⌈ l /2 ⌉]$ is less than $⌊ l /2 ⌋ + ⌈(k + 1) /2 ⌉ + ⌈(g + 1) /2 ⌉$ elements in $A \cup B \cup C$ , and it is easily verified that $⌊ l /2 ⌋ + ⌈(k + 1) /2 ⌉ + ⌈(g + 1) /2 ⌉ \geq ⌈(l + k + g) /2 ⌉$ for all positive $l, k, g$ .
No element in $G [g - ⌊ g /2 ⌋ + 1.. g]$ can be the median of $A \cup B \cup C$ ; every element is greater than $⌈ g /2 ⌉ + ⌈ k /2 ⌉ + ⌈ l /2 ⌉$ elements in $A \cup B \cup C$ . Again, we have $⌈ g /2 ⌉ + ⌈ k /2 ⌉ + ⌈ l /2 ⌉ \geq ⌈(l + k + g) /2 ⌉$ for all positive $l, k, g$ .

Thus, we can safely prune the first $α \equiv min (⌈ l /2 ⌉, ⌊ g /2 ⌋)$ elements from $L$ and the last $α$ elements from $G$ . If $α = 0$ , it must be because $g = 1$ . In this case, it is easy to see that $m_{G}$ can be the median only if $k$ and $l$ are even and $m_{G} < K [k /2 + 1] and m_{G} < L [l /2 + 1]$ . If that is not the case, we can discard $G$ (note that $⌈ l /2 ⌉$ is always nonzero), and reduce the problem to the one solved in $(c)$ .

It is evident that the algorithm must reach its base case in $lo g a + lo g b + lo g c \leq 3 lo g (a + b + c)$ time, which is then solved in $lo g (a + b + c)$ time. Thus, it runs in $O (lo g (a + b + c))$ time.

$(c)$

The algorithm assumes $A [0] = - \infty$ , $B [0] = - \infty$ , $A [m + 1] = + \infty$ , $B [n + 1] = + \infty$ . All elements of $A$ and $B$ are distinct.

KSmallest (A [1.. m], B [1.. n], k) : l \leftarrow ⌈ \frac{min ( m , k ) - max ( 0 , k - n ) + 1}{2} ⌉ p_{A} \leftarrow max (0, k - n) - 1 + l do : p_{B} \leftarrow k - p_{A} l \leftarrow ⌈ l /2 ⌉ if A [p_{A}] > B [p_{B}] : if A [p_{A}] < B [p_{B} + 1] : return A [p_{A}] p_{A} \leftarrow p_{A} - l else if A [p_{A}] < B [p_{B}] : if A [p_{A} + 1] > B [p_{B}] : return B [p_{B}] p_{A} \leftarrow p_{A} + l

Let $e_{A}$ denote the number of elements of $A$ that occur at or before index $k$ in the merged array $A \cup B$ . The possible values of $e_{A}$ is restricted by $max (0, k - n) \leq e_{A} \leq min (m, k)$ . The algorithm performs binary search for $e_{A}$ on the subarray $A [max (0, k - n), min (m, k)]$ .

In each iteration, $p_{B}$ is selected such that $p_{A} + p_{B} = k$ .

If $A [p_{A}] > B [p_{B}]$ and
1. $A [p_{A}] < B [p_{B} + 1]$ , then $A [1.. p_{A}] \cup B [1.. p_{B}] = A \cup B [1.. k]$ , and since $A [p_{A}]$ is the greatest element in $A [1.. p_{A}] \cup B [1.. p_{B}]$ , it follows that $e_{A} = p_{A}$ and $A [p_{A}] = A \cup B [k]$ .
2. $A [p_{A}] > B [p_{B} + 1]$ , then the index of $A [p_{A}]$ in $A \cup B$ is strictly greater than $k$ . This implies $e_{A}$ must be strictly lesser than $p_{A}$ . We proceed with the binary search by discarding the right half.
Similar analysis for $A [p_{A}] < B [p_{B}]$ .

The algorithm must terminate since we know a solution exists and our search space shrinks geometrically with every iteration. When we have narrowed down the list of possible $e_{A}$ ‘s to a singleton, the algorithm guarantees that that value ( $p_{A}$ ) must be equal to $e_{A}$ . For $p_{A} = e_{A}$ , the checks specified above pass, and $e_{A}$ is returned.

The algorithm runs in $O (lo g k) \leq O (lo g m + n) \leq O (lo g m + lo g n)$ time.

Problem 3

FindFlip_{1} (A [1.. N]) : if N = 1 : if A [1] < 0 : return 0 if A [1] > 0 : return 2 m \leftarrow ⌈ N /2 ⌉ if A [m] > 0 : return m + FindFlip_{1} (A [m + 1.. N]) if A [m] < 0 : return FindFlip_{1} (A [1.. m]) FindFlip_{2} (A [1.. N]) : if A [1] < 0 : return 0 m \leftarrow 1 while 2 m < N and A [2 m] > 0 : m \leftarrow 2 m return m + FindFlip_{1} (A [m + 1.. min (2 m, N)])

$FindFlip_{1}$ performs a binary search on $A [1.. N]$ : If $A [m]$ is positive, either $A [m]$ is the last positive element in $A$ (in which case $FindFlip_{1} (A [m + 1.. N])$ is $0$ ), or the last positive element in $A$ lies in $A [m + 1.. N]$ ; In either case, its position is given by $m + FindFlip_{1} (A [m + 1.. N])$ . If $A [m]$ is negative, the last positive element must lie in $A [1.. m]$ , and hence its position is given by $FindFlip_{1} (A [1.. m])$ . $FindFLip_{1}$ follows the recurrence

T (N) = T (N /2) + O (1),

so $T (N) = O (lo g N)$ .

$FindFLip_{2}$ bounds the position of the last positive element in a range $A [m + 1.. min (2 m, N)]$ of length $\leq n$ , and then uses $FindFlip_{1}$ , which now runs in $O (lo g m) \leq O (lo g n)$ time. Finding the range takes $O (lo g n)$ time, thus $FindFlip_{2}$ runs in $O (lo g n)$ time.

Problem 4

If the elements have a total order, one can sort them and check for duplicates with a linear scan in $O (n lo g n)$ time.

AreDistinct (A [1.. n]) : QuickSort (A) for i = 1 to n - 1 : if A [i] \equiv A [i + 1] return false return true

If we also know bounds $l, m$ on the elements of $A$ , and space is not a constraint, this can be achieved in $O (n)$ time, discounting the time taken to initialize $B [l .. r]$ (once done, it can be used to run the algorithm several times on different inputs until $c$ overflows, so the linear time claim isn’t all that unreasonable):

Initialize B [l .. r] with zeros c \leftarrow 0 AreDistinct_{2} (A [1.. n]) : c \leftarrow c + 1 for i = 1 to n : if B [A [i]] \equiv c return false B [A [i]] \leftarrow c

Problem 5

Part a

Using the master theorem, we have

T (n) = 2 T (n /3) + 1 = i = 0 \sum l o g_{3} n 2^{i} = Θ (n^{l o g_{3} 2})

Part b

T (n) = 5 T (n /4) + n = i = 0 \sum l o g_{4} n 5^{i} n / 4^{i} = Θ (n^{l o g_{4} 5}) .

Part c

Use substitution.

T (n) = T (n - 1) + 2 \leq 2 n = Θ (n)

Part d

Substitution, again.

T (n) = 2^{n} + c (2^{n} - 1) = Θ (2^{n}) .

Part e

T (n) = T (n) + 1

Assume $n = 2^{k}$ and $T (2) = 1$ . Then,

T (2^{k}) = T (2^{k /2}) + 1 = lo g_{2} k .

Thus, $T (n) = Θ (lo g lo g n)$ .

Problem 6

The recurrences for the three algorithms are given by

T_{A} (n) = 5 T_{A} (n /2) + f (n), T_{B} (n) = 2 T_{B} (n - 1) + c, T_{C} (n) = 9 T_{C} (n /3) + g (n),

where $f (n) = Θ (n)$ and $g (n) = Θ (n^{2})$ .

T_{A} (n) = i = 0 \sum l o g_{2} n 5^{i} f (n / 2^{i}) .

Let $f (n) \leq C n$ for all $n \geq n_{0}$ . Let $k$ be the largest integer such that $n / 2^{k} \geq n_{0}$ . Let $M$ be the maximum value of $f (n)$ for $n < n_{0}$ .

T_{A} (n) \leq i = 0 \sum k 5^{i} f (n / 2^{i}) + M i = k + 1 \sum l o g_{2} n 5^{i} \leq C i = 0 \sum k 5^{i} n / 2^{i} + (M (5^{l o g_{2} n_{0} + 1} - 1) /4) 5^{l o g_{2} (n / n_{0}) + 1} = O ((5/2)^{l o g_{2} (n / n_{0})} n) + O (5^{l o g n}) = O (n^{l o g 5}) + O (5^{l o g n}) = O (n^{l o g 5}) .

$T_{A} (n) \geq n^{l o g_{2} 5}$ , so $T_{A} (n) = Θ (n^{l o g 5})$ .

It has been shown that algorithm $B$ is $Θ (2^{n})$ .

T_{C} (n) = i = 0 \sum l o g_{3} n 9^{i} g (n / 3^{i}) = Θ i = 0 \sum l o g_{3} n n^{2} = Θ (n^{2} lo g n) .

Algorithm $C$ has the best time complexity, since $n^{l o g_{2} 5/4} \geq lo g_{10} n$ for all $n$ .

Problem 7

SumIsX (S_{1} [1.. a], S_{2} [1.. b], x) : QuickSort (S_{1}) QuickSort (S_{2}) i \leftarrow 1 j \leftarrow b while i \leq a and j \geq 1 if S_{1} [i] + S_{2} [j] < x i \leftarrow i + 1 if S_{1} [i] + S_{2} [j] > x j \leftarrow j - 1 else return (i, j) return (NaN, NaN)

$SumIsX$ first sorts $S_{1}$ and $S_{2}$ . Assume a solution exists, say $S_{1} [c] + S_{2} [d] = x$ . At every iteration, either $i$ is incremented, or $j$ is decremented. Since the algorithm only terminates if either $i$ or $j$ exceeds bounds, we can conclude that one of these two states must be achieved on some iteration:

$i = c$ and $j > d$ , or
$j = d$ and $i < c$ .

In the first case, $S_{1} [i] + S_{2} [j]$ will be greater than $x$ , resulting in $j$ being decremented repeatedly until $j = d$ and the algorithm terminates positively. In the second case, $S_{1} [i] + S_{2} [j]$ will be lesser than $x$ , resulting in $i$ being incremented repeatedly until $i = c$ and the algorithm terminates positively.

If a solution does not exist, the loop will terminate in no more than $a + b$ iterations.

Sorting $S_{1}$ and $S_{2}$ takes $O (a lo g a + b lo g b) \leq O ((a + b) lo g (a + b))$ time, and searching for a solution takes $O (a + b)$ time. Thus, the algorithm runs in $O ((a + b) lo g (a + b))$ time.

NoNotes

Graph View

AS ALGO 1