Given two sorted (byincreasing order) arrays A and B of n elements each, give an

Question

Given two sorted (byincreasing order) arrays A and B of n
elements each, give an O(log n) time algorithm for finding the nthsmallest item among the
2n elements in A and B. Assume n is a power of 2, and that the 2nitems are distinct
(i.e., that no two of them are equal). Given two sorted (byincreasing order) arrays A and B of n
elements each, give an O(log n) time algorithm for finding the nthsmallest item among the
2n elements in A and B. Assume n is a power of 2, and that the 2nitems are distinct
(i.e., that no two of them are equal).

Explanation / Answer

If n = 1 then return the smaller of A[0] and B[0], Otherwisecompare A [(n/2) 1] to B[(n/2) 1]:

1. If A[(n/2) 1] > B[(n/2) 1] thenrecursively solve (and return the answer from) the problem thatconsists of the left half of A and right half of B (each half is ofsize n/2, and the (n/2)th smallest element among them).

2. If A[(n/2) 1] < B[(n/2) 1] thenrecursively solve (and return the answer from) the problem thatconsists of the right half of A and left half of B (each half is ofsize n/2, and the (n/2)th smallest element among them).

After a comparison, the half of an array that we“throw away” (in the sense that it is not part of therecursive call performed next) consists of items that are known tobe

           (1)Larger than n other items (hence “too large”), or

         (2)Smaller than n + 1 other items (hence “too small” to bethe answer); in either case the items “thrown away” areno longer candidates to be the answer we seek (so it is correct tothrow them away). The reason we seek the (n/2)th item in therecursive call (this is implicit to the recursive call) is that,before recursing, we threw away n/2 items that are smaller than theanswer we seek, so the answer we seek is now (n/2)th smallest (inthe subproblem we’re recursing on) rather than nthsmallest.

The running time is O(log n) because binary search runs inO(log n)time. After a comparison, the problem size has been reducedby a factor of two, i.e., we have T(n) = T(n/2) + c and T(1) = c0where c and c0 are constants (that the solution to this is O(log n)can be seen either by solving it, or by observing that therecursion tree is unary, has logarithmic height, and has a singlecomparison performed at each of its nodes).

Related Questions

Navigate

• Browse (All)
• Browse G
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.