9.3-8

Professor Olay is consulting for an oil company, which is planning a large pipeline running east to west through an oil field of n wells. The company wants to connect a spur pipeline from each well directly to the main pipeline along a shortest route (either north or south), as shown in Figure 9.2. Given the x- and y-coordinates of the wells, how should the professor pick the optimal location of the main pipeline, which would be the one that minimizes the total length of the spurs? Show how to determine the optimal location in linear time.
In order to find optimal placement we only need to find medians of y-coordinates. Claim:
The optimal y-cordinate is as follows:
a) If n is even then the optimal placement of the pipeline is either on the oil well whose y-coordinate is lower median or on oil well whose y-coordinate is upper median or anywhere between them.
b) If n odd then the optimal placement of pipeline is on the oil well whose y-coordinate is the median.
Proof:
We examine various cases in each we start out with the pipeline at a particular y-coordinate and see what happens when we move it. We denote s as the sum of north and south spurs and s' denotes the sum after we move the pipeline.
If n is even and we start the pipeline on or somewhere between oil wells whose y-coordinate are the lower median and upper median. if we move the pipeline by a vertical distance d with out crossing either of the the median wells, then n/2 of the oil wells will be d distance farther from the pipeline and n/2 of the oil wells will nearer to the pipeline. If we caculate the distance s' = s+nd/2 - nd/2 then s' = s. thus all the locations on or between the two medians is good.
Now suppose if the pipeline goes through the upper median oil well and if we increase the y-coordinate of the pipeline d- distance away(upwards) from upper median. Then there are n/2+1 oil wells farther from pipeline and n/2-1 oil wells nearer to oil well. If we calculate the distance $$s' \geq s+(n/2+1)d-(n/2-1)d $$ $$s' \geq s+2d$$ clearly s' is greater than s.we conclude that if we move the pipeline away from the upper median then it increases the total spur length. similarly if we move the pipeline away below lower median the spur length increases.
when n is even the optimal placement of pipeline is on or somewhere between oil wells whose y-coordinates are upper and lower medians.
Now lets consider n is odd if we start the pipeline at oil well whose y-coordinate is the median and move the pipeline y-coordinate by d distance. Then there are n+1/2 oil well farther from the pipeline and n-1/2 oil wells nearer to the pipeline. if we calculate the distance $$s' \geq s+ (n+1/2)d -(n-1/2)d $$ $$s' \geq s+ d $$ which greater than s. A symmetrical argument shows that moving the y-cordinate of pipeline below the median also increases the spur length. If n is odd then the optimal placement for the pipeline is the median. We use the linear-time-median algorithm.

9.3-9

Let X{1..n] and Y[1..n] be two arrays, each containing n numbers already in sorted order. Give an O(lg n)-time algorithm to find the median of all 2n elements in arrays X and Y .
If X is an array that has 1..n and let median m occurs at X[k]. Then there k elements less than equal m and n-k elements greater than equal m.If we combine both arrays X and Y the no of elements is 2n. If m is a median after combining two arrays it should have n to its left and n elements to the right including m. So for the left side to have n there n-k less than or equal to m(let x be no of elements in y which less than or equal to m n = k+x then x = n-k ). similarly for the right side k elements greater than or equal to m(let x be no of elements in y which greater than or equal to m n = n-k+x). If we can an in equality. $$Y[n-k] \leq X[k] \leq Y[n-k+1]$$ But we need to also consider when k = n. Then Y[0] will have any elements and $X[n] \leq Y[1]$. If the median k' > k then X[k] will not satisfy the above equation. Then $$X[k] \lt Y[n-k]$$. Similarly if we have K' < k then X[k] > Y[n-k+1]. Similarly the median can occur in X or Y. If it occurs Y array the comparisions will have the array names reversed(replace x with Y and Y with X).We can use above analysis to write the algorithm. We can use binary search to find the median.

FIND-TWO-ARRAY-MEDIAN(X,Y)
n = A.length
median = FIND-MEDIAN(X,Y,1,n,n)
If median not found
FIND-MEDIAN(Y,X,1,n,n)
return median
FIND-MEDIAN(X,Y,low,high,n)
If low < high
k = (low+high)/2
If k = n and X[n] = Y[1] then
return X[n]
else if $Y[n-k] \leq X[k] \leq Y[n-k+1]$
return X[k]
else if $X[k] > Y[n-k+1]$
FIND-MEDIAN(X,Y,low,k-1,n)
else
FIND-MEDIAN(X,Y,k+1,high,n)

9.3-7

Describe an O(n)-time algorithm that, given a set S of n distinct numbers and a positive integer $k \leq n$, determines the k numbers in S that are closest to the median of S.
Assume for simplicity that n is odd and k is even. If the set S was in sorted order, the median is in position n=2 and the k numbers in S that closest to the median are in positions (n − k)/2 through (n + k)/2. We first use linear time selection to fi nd the (n − k)/2, n/2, and (n + k)/2 elements and then pass through the set S to fi nd the numbers less than (n+k)/2 element, greater than the (n−k)/2 element, and not equal to the n/2 element. The algorithm takes O(n) time as we use linear time selection exactly three times and traverse the n numbers in S once(Use for loop to do comparisons to find element > (n-k)/2 and less than (n+k)/2 but not equal to n/2 ).

9.3-6

The kth quantiles of an n-element set are the k 1 order statistics that divide the sorted set into k equal-sized sets (to within 1). Give an O(n lg k)-time algorithm to list the kth quantiles of a set. The k quantiles of an n-element sorted array A are: A[\floor 1 n/k \rfloor],A[\lfloor 2 · n/k \rfloor], . . . ,A[\lfloor(k − 1) · n/k\rfloor]. We have as inputs an unsorted array A of distinct keys, an integer k, and an empty array Q of length k − 1 and we want to find the kth quantiles of A. QUANTILES(A, k,Q)
1. if k = 1 then return
2. else
3. n = length[A]
4. i = $\lfloor k/2 \rfloor$
5. x = $ SELECT (A, \lfloor i n/k \rfloor)$
6. PARTITION (A, x)
7. Add to list Q: QUANTILES(A[1]..A[i· n/k], \lfoor k/2 \rfloor, Q)
8. Add to list Q: QUANTILES(A[i·n/k + 1]..A[n],\lceil k/2 \rceil, Q)
9. return x
The output Q of the recursive algorithm QUANTILES contains the kth quantiles of A. The algorithm first finds the key that turns out to be the lower median of Q, and then partitions the input array about this key. So we have two smaller arrays that each contain at most (k−1)/2 of the k−1 order statistics of the original array A. At each level of the recursion the number of order statistics in the array is at most half the number of the previous array. Consider a recurrsion tree for this algorithm. At the top level we need to find k − 1 order statistics, and it costs O(n) to find one. The root has two children, one contains at most $\lfoor(k−1)/2\rfloor$ order statistics, and the other $\lceil (k−1)/2 \rceil$ order statistics. The sum of the costs for these two nodes is O(n). At depth i we find $2^i$ order statistics. The sum of the costs of all nodes at depth i is O(n), for $0 \leq i \leq log_{2} (k − 1)$, because the total number of elelements at any depth is n. The depth of the tree is $d = log_{2}(k − 1)$. Hence, the worstcase running time of QAUNTILES is $ \theta(n lg k)$.

9.3-5

Suppose that you have a “black-box” worst-case linear-time median subroutine. Give a simple, linear-time algorithm that solves the selection problem for an arbitrary order statistic.
we are given a median subroutine that takes A ,p and r as parameters and returns the median value of A[p..r] in O(n) time.Given the median below is the SELECT' algorithm for finding ith smallest element. The algorithm uses deterministic partitioning that is modified to take element to partition around as input parameter.
SELECT'(A,p,r)
if p == r then
return A[p]
x = MEDIAN(A,p,r)
q = PARTITION(A,x)
k = q-p+1
if i == k then
return a[q]
if i > k
SELECT'(A,q+1,r,i-k)
else
SELECT'(A,p,q-1,i)
Because x is the median of A[p..q] and it partition the array in to A[p..q-1] and A[q+1..r] of n/2 sizes. we have the recurrence $$T(n) \leq T(n/2)+O(n)$$ the above recurrence is master method case T(n) = O(n).

9.3-4

Suppose that an algorithm uses only comparisons to find the i th smallest element in a set of n elements. Show that it can also find the i - 1 smaller elements and the n - i larger elements without performing any additional comparisons.


Suppose that the algorithm uses m comparisons to find the ith smallest element x in a set of n elements. If we trace these m comparisons in the log, we can easily find the i - 1 smaller elements by transitivity. If x > a and a > b, then x > b can be deduced without actually performing a comparison between x and b. Similarly, the n - i larger elements can be found, too.

Say we can not decide that some element e is smaller or greater than x. Then we claim that the algorithm does not work properly, since an adversary could design an input in which e is the ith largest element instead of x. The i -1 and n -i smaller elements may be not in sorted order with respect to each but they are in sorted order with respect to the ith smallest element. What I mean we get i -1 and n-i smaller elements but it does'nt any thing about the relative order of the smaller or larger elements it means they are just smaller or larger than i.

9.3-3

Show how quicksort can be made to run in O(n lg n) time in the worst case, assuming that all elements are distinct.
The worst case for quick sort occurs when the split creates 0 and n-1 elements. $T(n) = T(n-1)+\theta(n)$. But if we select a median that gives us n/2 and n/2 split always then we can eliminate the worst case.
BEST-CASE QUICKSORT(A,p,r)
if p < r then $$i \leftarrow (r-p+1)/2 $$ $$ x \leftarrow SELECT(A,i)$$ $$ q \leftarrow PARTITION(A,x)$$ BEST-CASE QUICKSORT(A,p,q-1)
BEST-CASE QUICKSORT(A,q+1,r)
Because the BEST-CASE QUICKSORT recurses only on elements of size at most n/2(for even n n/2 and n/2 - 1 and for odd n n/2 and n/2). $$T(n) \leq 2 T(n/2) + \theta(n)$$ The running time for above recursion is similar to merge sort $O(n log n()$

9.3-2

Analyze SELECT to show that if n 140, then at least $\lceil n/4 \rcieil elements are greater than the median-of-medians x and at least $\lceil n/4 \rcieil elements are less than x. if we draw a 5 X 5 grid. we have 3n/10 greater than x and 3n/10 elements are less than x. 3 140/10 = 42 n/4 = 140/4 = 35

9.3-1

In the algorithm SELECT, the input elements are divided into groups of 5. Will the algorithm work in linear time if they are divided into groups of 7? Argue that SELECT does not run in linear time if groups of 3 are used.

for groups of we can. if we can draw the 7 x 7 grid figure to represent the elements. we know there are 4 elements below the median that are greater median. hence the no of elements greater than the median of medians is $4(n/14 - 2)$ = $2n/7 - 8$. So if we partition the array as in step 4 using x(median of medians) we will be left with $n - (2n/7 - 8) $ = $5n/7 + 8 $
we can use the same recursive equation as for the groups of 5 and plugin values
$$T(n) \leq T(n/7)+ T(5n/7+8)+\theta(n) $$ let T(n) = cn $$T(n) = cn/7 + 5cn/7+8c+\theta(n) $$ $$T(n) = 6cn/7+8c+\theta(n) $$ $$T(n) = cn/7 - (cn/7-8c-an) $$ $$cn/7-8c-an \geq 0$$ $$cn/7-8c \geq an$$ $$c( n-56/7) \geq an$$ $$c \geq 7an/ ( n-56)$$ if n> 56 then the above recurrence is satisfied for the value of c described as above. Similarly for groups 3. if we draw 3 x 3 grid. 2(n/6-2) = n/3-4. The no of elements left after partitioning are n - (n/3-4) = 2n/3+4. $$T(n) \leq T(n/3)+ T(2n/3+4)+\theta(n) $$ $T(n) = cn$ $$T(n) = cn/3+ 2cn/3+4c)+\theta(n) $$ $$T(n) = cn/3+ 2cn/3+4c+\theta(n) $$ $$T(n) = cn+4c+\theta(n) $$ $$T(n) = cn +4c+\theta(n) $$ the above recurrence is greater than cn since we have the residual elements($4c+\theta(n)$).
we can prove the lower bound on T(n) to see the minimum value for the recurrence.The lower bound occurs when we the even split where we get 3 x 3 grid elements and no column with elements less than 3. The no of elements greater than median of medians x is 2(n/6-1)+ 1. (The -1 is for median of medians group and also there is one element in the median of medians that is greater than median of medians).The no of elements left after step 4 is n - (2(n/6-1)+1)= n - n/3+1 = 2n/3+1. The recurrence is $$T(n) \geq T(n/3)+ T(2n/3+1)+\theta(n) $$ $T(n) = cn log n$ $$T(n) = cn logn/3+ c(2n log n/3+1)+\theta(n) $$ $$T(n) = cn logn/3+ 2cn log n/3+c+\theta(n) $$ $$T(n) = cn logn+c+\theta(n) $$ $$T(n) = cn logn+c+\theta(n) $$ The above recurrence is at least cn logn.

selection in worst case linear time

The selection in worst case uses insertion sort to sort in step 2. but you would think insertion sort worst case running time is $O(n^2)$.but we are only sorting groups of 5 elements we know insertion sort is linear time for smaller values of n/. remember it beats megesort for smaller values of n. hence the step is linear time. Also dont use selection in worst case linear time because in practice it has large constants and it gets reduced by 19/20 n. it takes a while to be really small. use random selection in practice.

9.2-4

9.2-4 Suppose we use RANDOMIZED-SELECT to select the minimum element of the array A = {3, 2, 9, 0, 7, 5, 4, 8, 6, 1}. Describe a sequence of partitions that results in a worst-case performance of RANDOMIZED-SELECT.
Worst case occurs when the recurence is $T(n) = T(n-1)+\theta(n)$ there two ways to do it. Parition from 0 -9 or from 9 -0. ex: {0} {3,2,9,0,7,5,4,8,6,1} {1} {3,2,9,0,7,5,4,8,6,1} .... {9} {9}{0,1,2,3,4,5,6,7,8} ... {0}

9.2-3

Write an iterative version of RANDOMIZED-SELECT. RANDOMIZED-SELECT(A,p,r) while(p < r) If p == r return A[r]; q = RANDOM-PARTITION(A,p,r) k = q-p+1 If i == k return A[i] If i > k p = q+1 i = i - k else q = q-1

9.2-2

Argue that the indicator random variable $X_k$ and the value $T(max(k - 1, n - k))$ are independent.
$X_k$ and $T(max(k - 1, n - k))$ are independent. Because $X_k$(sub array A[p..q] has exactly k elements k=1..n) is dependent on random choice made by the random-partition call and $T(max(k - 1, n - k))$ is making its own random choices because it is a different recursive call. Hence they are independent.

9.2-1

Show that RANDOMIZED-SELECT never makes a recursive call to a 0-length array.
RANDOMIZED-SELECT has two recursive calls for i < k and i >k. If i > k the values q is reduced by (q = q-1 see the method argument). If we assume i > k is called in every recursive call the q is decreased by 1 every time. The base case will return when p = q . The least values q can take is p when (q=p) we have 1-length array. So the recursion returns for 1-length array.

9.1-2

9.1-2 Prove the lower bound of $3\lceil n/2 \rceil - 2$ comparisons in the worst case to find both the maximum and minimum of n numbers. (Hint: Consider how many numbers are potentially either the maximum or minimum, and investigate how a comparison affects these counts.)

We need to analyze even and odd case separately.

n is Even: If n is even we will divide the numbers in to n/2 pairs and compare elements in pairs and keep the small elements in array and larger elements in another array(you can swap with in the array as well if changing the input is allowed). To compare n/2 with n/2 elements we need n/2 comparisons. We now have Small array and large array. The smallest element must be in smallest array and largest element must be in the largest array. We use MINIMUM(A) to find smallest element on small array similarly we can MAXIMUM(A) to find the largest on large array. This will take n/2 - 1 for MINIMUM and MAXIMUM operations. since n is even n/2 = $\lceil n/2 \rceil$ We can now add up all comparisons $$\lceil n/2\rceil+\lceil n/2\rceil-1+\lceil n/2\rceil-1$$ $$3\lceil n/2\rceil-2$$ n is odd: If n is odd assign maximum and minimum to the first element and divide the array in to (n-1)/2 pairs. Let compare elements in pairs and keep the small elements in array and larger elements in another array. To compare (n-1)/2 pairs of elements we need (n-1)/2 comparisons. we now have a small array with small numbers and large array with large numbers. The smallest element must in small array and similarly large element must be in large array. We can use MINIMUM(A) to find a smallest element on small array and MAXIMUM(A) on large array to find the largest element.This needs (n-1)/2 -1 for both arrays. Later we need to compare the first element which we assigned as maximum and minimum element with smallest and largest element to find smallest and largest element. It will take two comparisons. since n is even (n-1)/2 = $\lceil (n-1)/2 \rceil$ We can now add up all comparisons $$\lceil (n-1)/2\rceil+\lceil (n-1)/2\rceil-1+\lceil (n-1)/2\rceil-1+2$$ $$3\lceil (n-1)/2\rceil$$ $$3\lceil n/2 \rceil-3/2$$ since 2 > 3/2 .The no of comparisons are more when n is even. The worst case occurs when n is even.

9.1-1

9.1-1 Show that the second smallest of n elements can be found with n + lg n - 2 comparisons in the worst case. (Hint: Also find the smallest element.)

To find the smallest number n-1 comparisons are made. To find the smallest conduct a tournament every number looses exactly once except the smallest. If we draw a binary tree there are n leaves and n-1 non leaf nodes. Every non leaf node represents a comparison hence we need n-1 comparisons. To find the smallest number the second smallest number must have come out smallest in every comparison except with the smallest number. To find the second smallest number conduct another tournament to compares all these numbers. At most log n elements(the height of binary tree) were compared with smallest number.So finding the smallest of these will take $\lceil log n \rceil - 1$ the total number of comparisions are $n- 1+ \lceil log n \rceil - 1$

8-7

8-6

8-6 Lower bound on merging sorted lists

The problem of merging two sorted lists arises frequently. We have seen a procedure for it as the subroutine MERGE in Section 2.3.1. In this problem, we will prove a lower bound of 2n - 1 on the worst-case number of comparisons required to merge two sorted lists, each containing n items. First we will show a lower bound of 2n - o(n) comparisons by using a decision tree.

a. Given 2n numbers, compute the number of possible ways to divide them into two sorted lists, each with n numbers.

b. Using a decision tree and your answer to part (a), show that any algorithm that correctly merges two sorted lists must perform at least 2n - o(n) comparisons. Now we will show a slightly tighter 2n - 1 bound.

c. Show that if two elements are consecutive in the sorted order and from different lists, then they must be compared.

d. Use your answer to the previous part to show a lower bound of 2n - 1 comparisons for merging two sorted lists.

a. ${{2n}\choose {n}}$
b. $${{2n}\choose {n}}$$ $$2n!/{n!}^2}$$ using stirling approximation $$\sqrt{4\pi n}. (2n/e)^2/(\sqrt{2\pi n} e^{1/12n})^2$$ for binary tree there will be $2^h$ leaves $$2^h = 2n - log 2\pi n$$ $$2^h = 2n - O(n)$$ c. If two list are sorted by merge procedure and the list needed to be merged. Since the elements are in two different lists we dont know if they are equal or greater or less than to know the relationship we need to compare them and arrange in the final array according to the order.

d. Lets assume the elements in first sorted list $L = {l_1,l_2...1_n}$ and second sorted list as $R= {r_1,r_2,r_3,r_4..r_n}$ if the elements in L list are all equal and greater than every element in R list. Then the merge procedure will compare the first element($l_1$) in the L list to every element in L the number of comparisons are n-1 and also according to c we need to compare two elements if they are consecutive in sorted order and from different list. Now since $l_1$ is greater than every element in R list we compare n times. Hence the running time is 2n -1.

8-5

8-5 Average sorting Suppose that, instead of sorting an array, we just require that the elements increase on average. More precisely, we call an n-element array A k-sorted if, for all i = 1,2....n k, the following holds:

$$ \frac{\sum_{j=i}^{i+k-1} A[j]} {k} \leq \frac{\sum_{j=i+1}^{i+k} A[j]} {k} $$ a. What does it mean for an array to be 1-sorted?
b. Give a permutation of the numbers 1,2...,10 that is 2-sorted, but not sorted. c. Prove that an n-element array is k-sorted if and only if $A[i] \leq A[i + k]$ for all i = 1,2,...,n -k.

d. Give an algorithm that k-sorts an n-element array in $O(n lg.n/k)$ time. We can also show a lower bound on the time to produce a k-sorted array, when k is a constant.
e. Show that we can sort a k-sorted array of length n in $O(n lg k)$ time. (Hint: Use the solution to Exercise 6.5-9. )
f. Show that when k is a constant, k-sorting an n-element array requires $ \Omega(n lg n)$ time. (Hint: Use the solution to the previous part along with the lower bound on comparison sorts.)
a. It is sorted.c has the answer for this puzzle for 1 sorted the it should satisfy $A[i] \leq A[i + 1]$ . hence the i+1 should always be greater than ith element where i is from 1..n.
b. Any permuatation that violates $A[i] \leq A[i+2]$ will work. ex: 1 3 2 4 5 6 7 8 9 10.
c. from the inequality for k - sorted array. $$ \sum_{j=i}^i+k-1 A[j] \over k \leq \sum_{j=i+1}^i+k A[j]$$ cancelling k on both sides $$ \sum_{j=i}^i+k-1 A[j] \leq \sum_{j=i+1}^i+k A[j]$$ expanding summation $$ A[i]+...+A[i+k-1] \leq A[i+1]+..+A[i+k]$$ cancelling elements from A[i+1] to A[i+k-1] $$ A[i] \leq A[i+k]$$ d. if we split the array in to groups of n/k and sort each group of n/k elements using any comparison sort the running time is $O(n/k log n/k )$. but since we do it for k times the running time is $O(k.n/k. log n/k$ = $O(n log n/k )$ e. If we sort the array using d algorithm and we have k sorted list we build MIN-HEAP on first k elements and EXTRACT-MIN-HEAP and repeat this for n/k times the running time is O(n log k). f. we can use the decision tree for calculating the lower bound. The leaves of the decision tree are various permutations of k-sorted array. $$ {{n} \choose {k}} . {{n-k} \choose {k}} . {{n-2k} \choose {k}}..{{k} \choose {k}} $$ $$ n!/k!(n-k)! . (n-k)!/(n-2k!).k! . (n-2k)!/(n-3k)! k! ..... k!/0! k! $$ $$ n!/ {k!}^{n/k} $$ since it is binary the no of leaves at height h is $$ 2^h \geq n!/ {k!}^{n/k} $$ if k were a constant lets replace k with c $$ 2^h \geq n!/ c $$ applying log $$ h \geq log( n!/ c) $$ $$ h \geq log( n!)- log c $$ log c should be negative $$log c < 0$$ $$ c < 1$$ $$ h \geq n log( n)$$

8-4

Water jugs Suppose that you are given n red and n blue water jugs, all of different shapes and sizes. All red jugs hold different amounts of water, as do the blue ones. Moreover, for every red jug, there is a blue jug that holds the same amount of water, and vice versa.

Your task is to find a grouping of the jugs into pairs of red and blue jugs that hold the same amount of water. To do so, you may perform the following operation: pick a pair of jugs in which one is red and one is blue, fill the red jug with water, and then pour the water into the blue jug. This operation will tell you whether the red or the blue jug can hold more water, or that they have the same volume. Assume that such a comparison takes one time unit. Your goal is to find an algorithm that makes a minimum number of comparisons to determine the grouping. Remember that you may not directly compare two red jugs or two blue jugs.

a. Describe a deterministic algorithm that uses $\theta(n^2)$ comparisons to group the jugs into pairs.
b. Prove a lower bound of $ \Omega(n lg n)$ for the number of comparisons that an algorithm solving this problem must make.
c. Give a randomized algorithm whose expected number of comparisons is $O(n lg n)$, and prove that this bound is correct. What is the worst-case number of comparisons for your algorithm?

a. If we compare each red jug with each blue jug since there are n red jugs and n blue jugs we get $\theta(n^2)$.

b. The algorithms has to make a series of comparisons to group the jugs in to groups. We can view the comparisons as a decision tree. Every internal node will have a Red jug and a blue jug and three children less than red jug, greater than red jug and equal to red jug. The height of the decision tree is the worst case of comparisons the algorithm has to make to determine matching.To bound the height lets compute the total number possible matchings of n red and n blue jugs.

If we label n red jugs from 1..n and n blue jugs from 1..n then

${i,\pi(i)}$ for i = 1..n $\pi$ is a permutation on {1..n}

since every permutation of $\pi$ corresponds to a different outcome we have n! outcomes.(if we draw a decision tree it will have to for groupings of jugs). Now since every node has a branching factor of 3.let h be the height of the tree, The tree should have at most $3^h$ leaves. $$ n! \leq 3^h$$ $$ log_3 n! \leq h$$ $$ n log n \leq h$$(Stirling app.) $$h = \Omega(n log n)$$ c. Assuming R jugs are labeled from 1..n and red jugs from 1..n. The output of the algorithm will contain distinct pairs of (i,j) where i corresponds to red and j corresponds blue jug with equal quantity. The procedure Matchjugs needs one condition to be satisfied $|R|=|B|$ Match-Jugs(R,B)

If |R| = 0
then return
If |R| = 1
then return R(1),B(1)
else
$$r \leftarrow a randomly chosen jug in R$$ compare r to every jug of B
$$B_< \leftarrow all elements of B jug less than r$$ $$B_> \leftarrow all elements of B jug greater than r$$ $$b the one jug in b with same size as r$$ $$R_< \leftarrow all elements of B jug less than b$$ $$R_> \leftarrow all elements of B jug greater than b$$ output("r","b")
Match-Jugs($R_<,B_<$)
Match-Jugs($R_>,B_>$)
What about the running time? The analysis of the expected number of comparisons is similar to that of the quicksort algorithm in Section 7.4.2. Let us order the jugs as r1, . . . , rn and b1, . . . , bn where ri < ri+1 and bi < bi+1 for i = 1, . . . , n, and ri = bi . Our analysis uses indicator random variables Xi j = I {red jug $r_i$ is compared to blue jug $b_j$ } .

As in quicksort, a given pair ri and bj is compared at most once. When we compare $r_i$ to every jug in B, jug $r_i$ will not be put in either R< or R>. When we compare bi to every jug in R −{$r_i$ }, jug bi is not put into either B< or B>. The total number of comparisons is $$X = \sum_{i=1}^n−1 \sum_{j=i+1}^n Xij $$.

To calculate the expected value of X, we follow the quicksort analysis to arrive at $$E [X] = \sum_{i=1}^n−1 \sum_{j=i+1}^n Pr {r_i is compared to b_j } .$$ As in the quicksort analysis, once we choose a jug $r_k$ such that $r_i < r_k < b_j$, we will put $r_i$ in $R_<$ and $b_j$ in $B_>$, and so $r_i$ and $b_j$ will never be compared again. Let us denote $R_ij = {r_i , . . . , r_j }$. Then jugs $r_i$ and $b_j$ will be compared if and only if the Þrst jug in Ri j to be chosen is either ri or r j . Still following the quicksort analysis, until a jug from $R_ij$ is chosen, the entire set Ri j is together. Any jug in $R_ij$ is equally likely to be Þrst one chosen. Since $|R_ij |$ = j − i + 1, the probability of any given jug being the Þrst one chosen in $R_ij$ is 1/( j−i+1). The remainder of the analysis is the same as the quicksort analysis, and we arrive at the solution of $O(n lg n)$ comparisons.

Just like in quicksort, in the worst case we always choose the largest (or smallest) jug to partition the sets, which reduces the set sizes by only 1. The running time then obeys the recurrence T (n) = T (n − 1) + (n), and the number of comparisons we make in the worst case is $T (n) = \theta(n2).$