Question

Q. Explain how a divide and conquer algorithm for detecting whether or not the number 5 exists in an array would work. Your explanation should include:

- a description of your algorithm using psuedocode
- a proof of correctness of your algorithm
- an analysis of the runtime of the algorithm

Answer 1

A Divide and Conquer algorithm to search for an element in an unsorted array can be done by dividing the problem into smaller problems by size one less than the previous problem i.e we first compare the first element of the array of size 'n' with 5, if it is not equal then we recursively search for 5 in rest of the array whose size is now 'n-1'.

1) PSEUDOCODE:

divide_conquer(A, low, high, x) // In our case x=5 and A is the array where the element is to be searched and low is the lower index of A and high is the higher index of A

{

if (high < low)

{

return NOT_FOUND;

}

if (A[low] == x)

return FOUND;

else

return divide_conquer(A, low+1, high, x);

}

2) CORRECTNESS:

The algorithm is correct because if low in the first recursive call is equal to the key then we found it at first and this is the best case and if not we are searching the rest of the array for the key. Every recursive call just decreases the size of the array by 1 to search the key. Thus, ultimately we are searching every element of the array for the key.

3) TIME COMPLEXITY:

The recurrence relation can be written as:-

T(n) = T(n-1) + c, where T(n) is the time taken to search for the key in an array of size n.

T(0) = c, base case.

Now, if we substitute T(n-1) we get:-

T(n) = T(n-2) + c + c

Now, if we substitute T(n-2) we get:-

T(n) = T(n-3) + 3c

If we do this 'k' times we get:-

T(n) = T(n-k) + kc.

Now let n-k = 0.

or, k=n.

As T(0) =c, if we substitute k=n in the equation we get:-

T(n) = c(n+1)

Hence T(n) = O(n).