Question

Let A[1 · · · n] be an array of n elements and B[1 · · · m] an array of m elements. We assume that m ≤ n. Note that neither A nor B is sorted. The problem is to compute the number of elements of A that are smaller than B[i] for each element B[i] with 1 ≤ i ≤ m. For example, let A be {30, 20, 100, 60, 90, 10, 40, 50, 80, 70} of ten elements. Let B be {60, 35, 73} of three elements. Then, your answer should be the following: for 60, return 5 (because there are 5 numbers in A smaller than 60); for 35, return 3; for 73, return 7.

(a) Design an O(mn) time algorithm for the problem. (10 points)

(b) Improve your algorithm to O(n log m) time. (20 points) Hint: Use the divide and conquer technique. Since m ≤ n, you cannot sort the array A because that would take O(n log n) time, which is not O(n log m) as m may be much smaller than n.

Note: For this problem, you need to describe the main idea of your algorithms and briefly analyze their time complexities. You will receive the full 30 points if you give an O(n log m) time algorithm directly for (b) without giving any algorithm for (a).

Answer 1

Solution

Part a

• Pick one element from array B and for the selected element of array B scan the elements of array A one by one to find which element is larger and which is smaller.
• Print the element and the corresponding count of elements in A which are smaller than this element of array B.
• Follow the above steps for all the m elements of array B.

Complexity analysis

Since for each element of array B complete array A is scanned.

Number of elements in array A is n

Number of elements in array B is m

So the complexity of the above algorithm is O(mn)

Part b

Sort the elements of array B. Sorting of elements in array B takes O(mlogm) time complexity.

Create a new array C of size m which stores the count of elements of array A which are smaller than element B[i].

i.e C[0] stores count of elements smaller than B[0]

C[1] stores count of elements smaller than B[1]

C[2] stores count of elements smaller than B[2] and so in.

Initialize all the elements of array C to zero.

Scan the elements of array A one by one and follow the below mentioned steps:

• for each element x of A, perform the binary search in array B.
• Binary search is used to identify the elements in array B larger than x.
• Increment the count of all the values at the index which we identify using the binary search.

At the end after the array A is scanned completely at index i in array C , the count of all the elements that are smaller than B[i] is stored.

Since binary seach takes O(logm)

And binary search is performed n times.

So total time complexity = Time to sort array B + Time to identify smaller elements using binary search

= O(mlogm) + O(nlogm)

= O(nlogm) (since n>m)