Division and conquest algorithms design

Question

I need to design this algorithm using the paradigm of division and conquest (strong induction). I’m not getting out of place...

Let A and B be two vectors of integers such that the total number of integers in the two vectors is n, and x an integer number. Design a complexity algorithm O(n log n) for the problem of determining whether there are indices i and j such that A[i] + B[j] = x".

Answer 1

The algorithm would be something like this:

função z(int[n] A, int[n] B, int x) {     // Linha 1
    C = copy(B)                           // Linha 2
    sort(C)                               // Linha 3
    int i, k = -1                         // Linha 4
    for (i = 0; i < n && k == -1; i++) {  // Linha 5
        k = binary_search(C, x - A[i])    // Linha 6
    }                                     // Linha 7
    if (k == -1) return [-1, -1]          // Linha 8
    j = indexof(B, C[k])                  // Linha 9
    return [i, j]                         // Linha 10
}                                         // Linha 11

In this algorithm:

• copy is the function that creates a copy of an array.
• sort is the function that sorts an array.
• binary_search is the function that searches for an element in an ordered array using binary search and returns the position where the element is found. -1 is returned if the element is not found.
• indexof is the function that returns at which position of an array (possibly unordered) a given element is found.

The function returns a pair of elements that correspond to the positions [i, j] of the requested elements. If there are no i and j such that A[i] + B[j] = x, then [-1, -1] is returned.

The idea is to create an ordered copy of B called C. With this, you can scroll through each position of A using i as a counter and searching by binary search for the corresponding element in C in a position k. If the C search is never successful after the entire A array has been traversed, then [-1, -1] is returned. Otherwise, when the binary search is successful, the correct value of i is determined and then just search on B the element in C[k] to discover the value of j.

• The complexity of line 2 is O(n).

• The complexity of line 3 is O(n log n). To do this, just use an algorithm such as mergesort as sort.

• The loop of lines 5-7 runs in the worst case O(n) times.

• Each iteration of line 6 has a complexity of O(log n).

• Therefore, the total complexity of the 5-7 line loop is O(n log n).

• Line 9 has complexity O(n) in the worst case. A sequential search in B is sufficient.

• Lines 4, 8 and 10 have complexity O(1).

So the total complexity is O(n) + O(n log n) + O(1) + O(n log n) + O(1) + O(n) + O(1) and that’s O(n log n).

There is one but only. This is not a division-and-conquer algorithm. However, it may serve you at least as a basis for producing one that is.