\documentstyle[11pt,handout]{article}
\begin{document}
\input{macros}
\input{/home/rraj/Courses/3390/S99/macros/localmacros}
\thispagestyle{empty}
\setlength{\parindent}{0pt}
\setlength{\parskip}{1.8ex}
\newcommand{\k}{{\it key}}
\newcommand{\twolists}{{\sc 2ListSelect}}
\newcommand{\TL}{T_L}
\newcommand{\TR}{T_R}

\head{3390}{Analysis of Algorithms}{Winter 2000}{8 February 2000}{10}

\begin{center}
\Large{\bf Sample Solution to Problem Set 2}
\end{center}

\bigskip 

{\bf Problem 6 of PS 1 (5 + 5 + 10 = 20 points)} Problem 8--4, page
169.  In part~(c), your modification must maintain the expected
$\Theta(n \lg n)$ running time of the algorithm.

{\bf Answer:} This problem concerns a version of quicksort that
simulates tail recursion.  (Note that the partition procedure defined
in text and used in this problem behaves differently in slight details
than the one we covered in class.)
\begin{itemize}
\item [{\bf (a)}] We can prove the correctness of {\sc Quicksort'} by
  induction on the length of the array.  For the base case, when the
  array is of length $0$ or $1$, the algorithm is trivially correct.
  
  Now consider the induction step.  {\sc Quicksort'} first partitions
  the given array around the pivot element.  So all elements in
  $A[p..q]$ are less than or equal to $A[q + 1.. r]$.  This implies
  that it suffices to sort $A[p..q]$ and $A[q + 1.. r]$ separately.
  Next, {\sc Quicksort'}$(A, p, r)$ recursively calls {\sc Quicksort'}
  on the left half, the correctness of which follows from the
  induction hypothesis.  Finally, $p$ is set to $q + 1$ and another
  iteration of the while-loop is executed.  Executing another
  iteration of the while-loop is equivalent to making a recursive call
  to {\sc Quicksort'}$(A, q + 1, r)$, the correctness of which again
  follows from induction.  This completes the correctness proof.
  
\item[{\bf (b)}] Consider the instance when the array $A$ is sorted.
  In this case, whenever partition is called on a subarray with $m$
  elements, the left side of the partition contains $m - 1$ keys.
  Therefore, the first call of {\sc Quicksort'} will be on $n$
  elements, which will lead to a recursive call on $n - 1$ elements,
  which will lead to one on $n - 2$ elements, and so on.  Thus, when
  the final recursive call is made (on $1$ element), the stack will
  contain information about $n - 1$ other recursive calls.  Therefore,
  the stack depth will be $\Theta(n)$.
  
\item[{\bf (c)}] The idea is to recurse on the smaller half only.
  This way, we ensure that whenever we increase the stack depth by
  $1$, we decrease the input size by a factor of $2$ at least.  This
  implies that the stack depth cannot grow more than $\lg n$.
  Here is the implementation of quicksort that achieves this.

\begin{tabbing}
{\sc Quicksort''}$(A, p, r)$\\
1.  \= \mywhile\ \= $p < r$\\
2. \> \> do $\triangleright$ Partition and sort left subarray\\
3. \> \> $q \leftarrow \mbox{{\sc Partition}}(A, p, r)$\\
4. \> \> \myif\ \= $q - p + 1 < r - q$\\
5. \> \> \> {\sc Quicksort''}$(A, p, q)$\\
6. \> \> \> $p \leftarrow q + 1$\\
7. \> \> \myelse \\
8. \> \> \> {\sc Quicksort''}$(A, q+1, r)$\\
9. \> \> \> $r \leftarrow q$
\end{tabbing}
\end{itemize}

{\bf 1. (2 + 3 + 10 + 5 = 20 points)} Problem 1--3, page 18.

\begin{itemize}
\item[{\bf (a)}]
The five inversions are: $(1,5) (2,5) (3,4) (3,5) (4,5)$.

\item[{\bf (b)}]
 The reverse-sorted array $[n, n-1, \ldots, 2, 1]$ has the most
  number of inversions.  It has $n-1 + n-2 + \ldots + 2 + 1 =
  n(n-1)/2$ inversions.
  
\item[{\bf (c)}]
 We will show that if $T(A)$ is the running time of insertion
  sort on input $A$ and $I(A)$ is the number of inversions in $A$,
  then $T(A)$ is $\Theta(I(A) + n)$.
  
  Consider what happens in the $j$th for loop of insertion sort.  (See
  pseudocode on page 8 of text.)  At the start of this for loop, all
  of the elements in $A[1..j-1]$ have been sorted.  In the for loop,
  we first set $\k$ to $A[j]$ (line 2) and then compare it with
  elements $A[j-1]$, $A[j-2]$, \ldots, (the while-loop in lines 5
  through 7) until an element smaller than or equal to $\k$ is found.
  Thus the total number of executions of the while-statement is
  exactly equal to 1 more than the number of elements that are in the
  first $(j - 1)$ positions and are greater than $A[j]$.  But the
  elements that are in the first $(j - 1)$ positions and are greater
  than $A[j]$ exactly correspond to the number of inversions of the
  form $(\cdot, j)$ in $A$.  Thus, if we add over all of the for
  loops, we get that the total number of while loop executions is
  $I(A) + (n - 1)$.  Since there are only a constant number of
  operations in each while loop, the running time of insertion sort is
  $\Theta(I(A) + n)$.
  
\item[{\bf (d)}]
 We define a recursive procedure {\sc Count-Inversions} as
  follows.  Let $n$ be the size of the given array.  If $n \le1$, then
  we simply return $0$.  Otherwise, we divide the array of $n$
  elements into two parts, one of size $\lfloor n/2 \rfloor$ and the
  other of size $\lceil n/2 \rceil$, as in {\sc Mergesort}.  Then, we
  recursively call {\sc Count-Inversions} on the two subarrays.
  Finally, we call the procedure {\sc Cross-Count-Inversions}, which
  is a modification of {\sc Merge}, in which we count the number of
  inversions involving an element in $A_1$ and an element in $A_2$.
  We call these inversions {\em cross-inversions}.

\begin{tabbing}
{\sc Count-Inversions}$(A)$\\
1.  \= \myif\ $|A| \le 1$, \ret\ $0$;\\
2. \> divide $A$ into two halves $A_1$ and $A_2$ of size $\lfloor n/2 \rfloor$ and $\lceil n/2 \rceil$, respectively. \\
3. \> $c_1 = $ {\sc Count-Inversions}$(A_1)$;\\
4. \> $c_2 = $ {\sc Count-Inversions}$(A_2)$;\\
5. \>\ret\ $c_1 + c_2 + \mbox{{\sc Cross-Count-Inversions}}(A_1, A_2)$;
\end{tabbing}

The procedure {\sc Cross-Count-Inversions} follows the same outline as
{\sc Merge}, with two pointers, one traversing each of the two
subarrays.  Let the pointers traversing arrays $A_1$ and $A_2$ be
$p_1$ and $p_2$, respectively.  The only modification one needs to do
to {\sc Merge} is that whenever the element pointed to by $p_2$ is
found to be less than the element pointed to by $A_1$, we add to our
count the number of elements in $A_1$ that are to the right of (and
including) the element pointed to by $p_1$.  This is precisely the
number of cross-inversions that the element pointed to by $p_2$ is
involved in.  This procedure is clearly a $\Theta(n)$ worst-case time
procedure.  

The running-time of {\sc Count-Inversions} thus has the same
recurrence as {\sc Mergesort}, yielding a $\Theta(n \lg n)$ time.
\end{itemize}

{\bf 2. (2 + 8 + 5 = 15 points)} A {\em bitonic}\/ sequence is a
sequence of numbers that monotonically decreases and then
monotonically increases.  That is, a sequence $X = x_1, x_2, \ldots,
x_n$ is bitonic if there exists a $t$ in $[1, n]$ such that $x_{i+1} <
x_i$ for $1 \le i < t$ and $x_{i+1} > x_i$ for $t \le i < n$.
\begin{Itemize}
\item[{\bf (a)}]
Give an $O(1)$ time algorithm to find the maximum of a given bitonic sequence.

{\bf Answer:} The maximum of the first and last elements yield the
maximum of the sequence.

\item[{\bf (b)}]
Give an $O(\lg n)$ time algorithm to find the minimum of a given bitonic
sequence of length $n$.  Briefly justify the correctness of your algorithm.

{\bf Answer:} The minimum of a bitonic sequence is the unique element
$x_i$ in $X$ that satisfies one of the following three conditions: (i)
$i = 1$ and $x_i < x_{i+1}$; (ii) $i = n$ and $x_{i-1} > x_i$; (iii)
$1 < i < n$, $x_{i-1} > x_i$, and $x_{i+1} > x_i$.  

We use a recursive binary-search procedure.  If the length of the list
is $1$, then simply return the lone element.  Otherwise, if any of the
conditions (i) or (ii) hold, we simply return the appropriate element.
If none of these two conditions hold, we probe the middle element, say
$x_i$ of the list.  If $x_i$ satisfies condition (iii), we return this
element.  Otherwise, either $x_{i-1} < x_i < x_{i+1}$ or $x_{i-1} >
x_i > x_{i+1}$.  In the former case, we make a recursive call on the
right half of the list.  In the latter case, we make a recursive call
on the left half of the item.

The recurrence for the running-time is $T(n) \le T(\lfloor n/2
\rfloor) + \Theta(1)$, which yields an $O(\lg n)$ worst-case running
time.

\item[{\bf (c)}]
Give an $O(\lg n)$ time algorithm to find the median of a given bitonic
sequence.  ({\em Hint:} Use part~(b).)

{\bf Answer:} We first obtain the minimum using part~(b).  We now have
two sorted lists and we need to find the median of the combined list.
This problem is a special case of the bonus problem below.  The idea
is to compare the medians of the two lists and then (based on the
comparison) eliminate half of each list and then iterate.  See the
solution to the bonus problem for full details.
\end{Itemize}

{\bf 3. (11 points)} Exercise~10.3--9, page 192.

{\bf Answer:} We assume that the $x$-axis runs east-west and the
$y$-axis north-south.  Let the $n$ oil-field locations have
coordinates $(x_i, y_i)$, $1 \le i \le n$.  The first observation we
make is that the particular values of the $x$-coordinates do not make a
difference since the distance of an oil-field from the oil pipeline is
just the difference in the $y$-coordinates.  We now show that the
pipeline should be placed along that line parallel to the $x$-axis that
has a $y$-coordinate equal to the median of the $n$ $y$-coordinates $y_1$,
$y_2$, \ldots, $y_n$.  We assume without loss of generality that $y_1
\le y_2 \le \ldots y_n$.

Let $y = p$ denote the location of the pipeline.  Then, the sum of
the distances of the pipeline to the oil-fields equals:
\[
\sum_{y_i \le p} (p - y_i) + \sum_{y_i \ge p} (y_i - p).
\]
We claim that $y = y_{\lceil n/2 \rceil}$ is an optimal location for
the pipeline.  

Let the line $y = y^*$ yield an optimal location.  If $y^* = y_{\lceil
  n/2 \rceil}$, then there is nothing to prove.  Consider the case
$y^* > y_{\lceil n/2 \rceil}$.  Let $k$ be the largest $i$ such that
$y_i \le y^*$.  If $k > \lceil n/2 \rceil$, then consider the sum of
distances when the pipeline is placed at $y = y^* - \eps$, where
$\eps$ is a small constant.  This is exactly the cost of the pipeline
$y = y^*$ plus $\eps (n - k) - \eps k = \eps (n - 2k)$.  Since $k >
\lceil n/2 \rceil$, this implies the new location has cost smaller
than the location $y = y^*$, thus yielding a contradiction.  On the
other hand, if $k = \lceil n/2 \rceil$, then the cost of the pipeline
$y = y_{\lceil n/2 \rceil}$ is no more than that of $y = y^*$.

We now consider the case $y^* < y_{\lceil n/2 \rceil}$.  Let $k$ be
the largest $i$ such that $y_i \le y^*$.  If $k < \lfloor n/2
\rfloor$, then consider the sum of distances when the pipeline is
placed at $y = y^* + \eps$, where $\eps$ is a small constant.  This is
at most the cost of the pipeline $y = y^*$ plus $\eps (k) - \eps (n -
k) = \eps (2k - n)$.  Since $k < \lceil n/2 \rceil$, this implies the
new location has cost smaller than the location $y = y^*$, thus
yielding a contradiction.  On the other hand, if $k = \lfloor n/2
\rfloor$, then the cost of the pipeline $y = y_{\lceil n/2 \rceil}$ is
no more than that of $y = y^*$.

Now, the problem reduces to finding the element of rank $\lceil n/2
\rceil$ from the list $y_1, y_2, \ldots, y_n$, which can be done in
$O(n)$ time using {\sc Select} in $O(n)$ time.

{\bf 4. (10 + 10 = 20 points)} Let the {\em multi-selection problem\/}
be defined as follows. The input is a set $S$ of $n$ distinct keys
drawn from some totally ordered universe, and a set of $k+1$ integers
$r_i$ such that $1=r_0<r_1<\cdots<r_k=n+1$.  The output is a partition
of $S$ into $k$ sets $S_0,\ldots,S_{k-1}$ such that $S_i$ is the set
of all keys with ranks greater than or equal to $r_i$ and strictly
less than $r_{i+1}$.
\begin{Enumerate}
\item[(a)] Give an $O(n\lg k)$ time comparison-based algorithm for the
  multi-selection problem.  You may assume for simplicity that $k$ is
  a power of $2$.
  
  {\bf Answer:} We give a divide-and-conquer algorithm.  We find the
  element of rank $r_{\lceil k/2 \rceil}$ in $S$ using {\sc Select} in
  $O(n)$ time.  We next partition the set $S$ into two groups around
  this element, while keeping the element of rank $r_{\lceil k/2}$ in
  the right group.  We then recursively call the multiselection
  procedure on the two groups, the left one with the ranks $r_0, r_1,
  \ldots, r_{\lceil k/2 \rceil - 1}, r_{\lceil k/2 \rceil}$, and the
  right one with the ranks $1, r_{\lceil k/2 \rceil + 1} - r_{\lceil
    k/2\rceil} + 1, \ldots, r_{k} - r_{\lceil k/2 \rceil} + 1$. We
  thus get the following recurrence for the running time:

\[
T(n, k) \le \Theta(n) + T(m, k/2) + T(n - m, k/2).
\]
The above recurrence is written as a two-variable recurrence, but it
is easy to solve using the recursion tree approach.  We note that the
contribution of each level is $\Theta(n)$, and the number of levels is
$\Theta(\lg k)$ since the number of keys goes down by half in each
level.  This establishes that the running time of the above
multi-selection algorithm is $\Theta(n \lg k)$.

\item[(b)] Show that any comparison-based algorithm for the
  multi-selection problem requires $\Omega(n\lg k)$ comparisons in the
  worst case.  You may assume for simplicity that $n$ is evenly
  divisible by $k$.  ({\em Hint:} You may make use of the fact that
  $\lg m!=m\lg m-\Theta(m)$.)
  
  {\bf Answer:} We use the decision-tree method to establish a lower
  bound for the multi-selection problem.  Any comparison-based
  multi-selection algorithm can be written as a decision-tree in which
  each node represents a comparison.  (This is exactly like the
  structure we derived for insertion sort in class.)  
  
  Let ${\cal A}$ be any comparison-based algorithm for multi-selection
  over $n$ elements and $k$ ranks and let $h$ and $N$ be the height
  and the number of nodes the decision-tree associated with ${\cal
    A}$.  The number of leaf nodes should be at least the number of
  different output configurations.  The number of different output
  configurations equals
\[
{n \choose r_1} {n - r_1 \choose r_2 - r_1} {n - r_2 \choose r_3 - r_2} \cdots = \frac{n!}{r_1! (r_2 - r_1)! (r_3 - r_2)! \cdots 1}.\]

Consider the specific instance in which $r_i = in/k$.  In this case,
the right hand side of the above equality reduces to $n!/((n/k)!)^k$.  
Therefore, the height of the tree $h$ must satisfy:
\begin{eqnarray*}
h & \ge & \lg(n!) - k \lg((n/k)!)\\
&  = & n \lg n - \Theta(n) - k (n\lg (n/k)/k - \Theta(n/k))\\
& = & n \lg n - n \lg n + n \lg k + \Theta(n)\\
& = & \Omega(n \lg k).
\end{eqnarray*}

Since the height of the tree is a lower bound on the number of
comparisons needed in the worst-case, the desired claim is proved.
\end{Enumerate}

{\bf 5. (2 + 5 + 5 + 5 + 2 + 5 = 24 points)} Problem 13--3, page 260.

{\bf Answer:} 
\begin{itemize}
\item[{\bf (a)}] This part follows directly from the definition of the
  total internal path length, since $P(T)$ is the sum, taken over all
  of the nodes of the tree $T$, of the depth of the node.
  
\item[{\bf (b)}] By the definition of $P(\TL)$ and $P(\TR)$, $P(T)$
  equals the sum of $P(\TL)$, $P(\TR)$, and the number of nodes in
  $\TL \cup \TR$ (to account for the increase in depth of all the
  nodes in tree $T$).  Therefore,
\[ P(T) = P(\TL) + P(\TR) + n - 1.\]

\item[{\bf (c)}] If $x$ is the first element to be inserted into the
  binary search tree, then after all of the $n$ elements are inserted,
  we have a tree $T$ with root $x$ such that the left subtree $T_{L}$
  of $x$ contains all elements with keys less than $x$ and the right
  subtree $T_{R}$ contains all elements with keys greater than $x$.
  For a given $i$, $0 \le i < n$, the probability that the number of
  nodes in $T_{L}$ equals $i$ is exactly $1/n$ since this is the
  probability that the rank of $x$ is $i + 1$.  Since the number of
  nodes in $T_{R}$ is $n - 1$ minus the number of nodes in $T_{L}$,
  the formula in part~(b) yields the following recurrence for the
  average internal path length of a randomly built binary search tree
  with $n$ nodes.

\[ P(n) = \frac{1}{n} \sum_{i = 0}^{n -1} (P(i) + P(n - i - 1) + n -1).\]

\item[{\bf (d)}] This is straightforward algebra.
\begin{eqnarray*}
P(n) & = & \frac{1}{n} \sum_{i = 0}^{n -1} (P(i) + P(n - i - 1) + n -1)\\
& = & \frac{1}{n} \sum_{i = 0}^{n -1} P(i) +  \frac{1}{n} \sum_{i = 0}^{n -1} P(n - i - 1) + \frac{n(n-1)}{n}\\
& = & \frac{2}{n} \sum_{i = 0}^{n -1} P(i) + \Theta(n),
\end{eqnarray*}
where the finally equality follows by noticing that the sum of $P(n -
i -1)$, $i$ going from $0$ to $n - 1$, is the same as the sum of $P(i)$,
$i$ going from $0$ to $n - 1$.

\item[{\bf (e)}] This recurrence is exactly the same as for randomized
  quicksort.  We also know that the base case is $P(1) = 0$.
  So we can show, as in randomized quicksort, that $P(n) = O(n \lg
  n)$.
  
\item[{\bf (f)}] Let the $n$ elements inserted into the binary search
  tree be $A[1]$, $A[2]$, \ldots, $A[n]$, listed in the order of their
  insertion.  Then every element $A[i]$, $i > 1$, is compared with the
  first element $A[1]$ at the time of insertion.  Correspondingly, the
  only element to which every other element is compared in quicksort
  is the first pivot element.  This is achieved by an implementation
  of the {\sc Partition} procedure, in which we make a pass through
  the array and compare all other elements with the pivot element, and
  placing the lesser elements on the left half, while placing the
  greater elements on the right half of the array.  For this purpose,
  we store the partitioned array in a new location, thus not sorting
  in place.
  
  Now consider the following implementation of quicksort.  We set the
  first element to be the pivot element.  We partition the array into
  two subarrays, as described above, and recurse.  More precisely, 

\begin{tabbing}
{\sc New-Quicksort}$(A, p, r)$\\
1.  \= \myif\ $p <  r$ then\\
2.  \> $x \leftarrow A[p]$\\
3. \> \myfor\ \= $i \leftarrow p + 1$ to $r$\\
4. \>\> \myif\ $A[i] < A[p]$ place $A[i]$ into the next position in temporary array $A_<$\\
5. \> \> \myelse\ place $A[i]$ into the next position in temporary array $A_>$\\
6. \> copy elements from $A_<$, then $A[p]$, then $A_>$, in that order into $A[p..r]$\\
7. \> Let $q$ be the new position of $x$ in $A$\\
8. {\sc New-Quicksort}$(A, p, q - 1)$\\
9. {\sc New-Quicksort}$(A, q + 1, r)$
\end{tabbing}

The proof that the comparisons made during the binary tree insertions
and the {\sc New-Quicksort} computation are exactly the same follows
from an inductive argument.  For the base case, when we have one
element only, there is no comparison in either case.  For an
$n$-element array, the comparisons in the binary search tree consist
of (i) the comparisons of the first element $A[1]$ with every other
element, (ii) the comparisons of the elements less than $A[1]$ as they
are inserted in the left subtree of $A[1]$, and (iii) the comparisons
of the elements less than $A[1]$ as they are inserted in the right
subtree of $A[1]$.  In {\sc New-Quicksort}, we perform the comparisons
listed in (i) and then recursively call {\sc New-Quicksort} on the
elements less than $A[1]$ recursively call {\sc New-Quicksort} on the
elements greater than $A[1]$.  By induction, the two recursive calls
lead to comparisons exactly the same as the ones made in (ii) and
(iii).  This yields the desired result.
\end{itemize}

{\bf 6. (10 points)} Show that any arbitrary $n$-node binary search
tree can be transformed into any other arbitrary $n$-node binary
search tree using $O(n)$ rotations.  ({\em Hint:}\/ First show that at
most $n - 1$ right rotations suffice to transform the tree into a
right-going chain.)

{\bf Answer:} Since left and right rotations are symmteric, we observe
that if a binary tree $T$ can be transformed into a right-going chain
using at most $n - 1$ right rotations, then a right going chain can be
transformed into $T$ using at most $n - 1$ left rotations.  If $T$ was
transformed into a right-going chain via the sequence $T = T_0, T_1,
T_2, \ldots, T_k = $ right-going chain, then the right-going chain can
be transformed into $T$ using left rotations obtaining the sequence
$T_k, T_{k-1}, T_{k-2}, \ldots, T_2, T_1, T_0 = T$.

Thus, if we show that any binary tree $T$ can be transformed into a
right-going chain using at most $n - 1$ rotations, then we can
transform a given tree $T_1$ to $T_2$ by first transforming $T_1$ to a
right-going chain using at most $ n - 1$ right rotations and then
transforming the right-going chain to $T_2$ using at most $n - 1$ left
rotations.  Thus, in all $O(n)$ rotations.

Consider an arbitrary binary tree $T$.  If the root has a left child,
then a right rotation around the root increases the number of nodes in
the right-going path by $1$.  So we repeatedly perform rotations
around the root until the root has no left child.  We then proceed
along the right-going path and find the first node $u$ that has a left
child.  We perform a right rotation around $u$.  This again increases
the number of nodes on the right-going chain by one.  We continue in
this manner until every node is on the right-going path of the tree
which implies that the tree is a right-going chain.

Since every rotation increases the number of nodes on the right-going
path by $1$ and initially the length of the right-going path is at
least $1$, the number of rotations needed to obtain a right-going
chain is at most $n - 1$.

{\bf Bonus Problem (10 points)} Design and analyze an efficient
algorithm to select a key of a given rank from a set of $m+n$ keys
given in the form of two sorted lists, one of length $m$ and the other
of length $n$.  For convenience, you may assume that the $m+n$ keys
are all distinct.  ({\em Hint:}\/ A running time of
$O(\log\min\{m,n\})$ is achievable.)

{\bf Answer:} We present an algorithm for selecting an element of arbitrary
rank $k$ from the two sorted lists.  The median can then be computed by
setting $k = \lfloor (m+n)/2 \rfloor$ or $k = \lceil (m + n)/2 \rceil$.  Let
the two sorted lists be $A[1..m]$ and $B[1..n]$.  Without loss of generality,
assume that $n \le m$.  The worst-case running time of our algorithm will turn
out to be $O(\log n)$.

The basic idea is to reduce the size of array $B$ by half in each iteration by
performing only a consant number of operations.  Thus, the number of
iterations will be $O(\log n)$ and so will the worst-case running time be.  In
the following pseudocode, $A$ and $B$ are the two given arrays, $p$ and $r$
are two indices of array $B$, $p \le r$, and $k$ is the rank that we are
seeking.  The algorithm returns the element of rank $k$ from the two sorted
lists $A$ and $B[p..r]$.  In order to find the median, we simply call $\twolists(A,
B, 1, n, \lfloor (m+n)/2 \rfloor)$.

\begin{tabbing}
$\twolists(A, B, p, r, k)$\\
\\
1. \= \myif\ \= $k < r - p + 1$ then \hs // No point in searching
$B[p+k..r]$\\
2. \> \> then $r = p + k - 1$\\
3. \> \myif\ $p = r$ then \hs // $B$ has only one element\\
4. \> \> \myif\ $A[k-1] > B[p]$ then \ret\ $A[k-1]$\\
5. \> \> \myelse\ \myif\ $A[k-1] < B[p]$ then \ret\ $\min\{A[k], B[p]\}$\\
6. \> \myelse\ \hs // $B$ has more than one element\\
7. \> \> $\ell = \lfloor (r - p + 1)/2 \rfloor$ \hs // $\ell$ is half the size of $B$\\
8. \> \> \myif\ $A[k - \ell] > B[p + \ell - 1]$ \hs // compare the middle element
of $B$ with appropriate element of $A$\\
9. \> \> then \ret\ $\twolists(A, B, p + \ell, r, k - \ell)$ \hs // discard first half of $B$\\
10. \> \> \myelse\ \ret\ $\twolists(A, B, p, p + \ell - 1, k)$ \hs // discard second half of $B$
\end{tabbing}

The worst-case running time of the algorithm is given by the recurrence $T(n)
= T(n/2) + \Theta(1)$, which yields $T(n) = \Theta(\log n)$ (like binary
search).

\end{document}

