Let A be an unsorted array of n numbers FindMinA If size of

Let A be an unsorted array of n numbers FindMin[A] If size of A is at most 5 then return the minimum value in this array. Else {Partition A into three arrays A1, A2, A3 such that each subarray has size n x=FindMin[A1] y=FindMin[A2] z = FindMin[A3] Return (Minimum of x, y, z)} State the recurrence for the running time of FindMin[A], i.e. T(n)=... State what the above recurrence resolves to in terms of n i.e. T(n) is theta (...). You do not need to prove your answer. Prove by induction on the size of A that FindMin[A] correctly finds the minimum value in A. (You get 1 mark for proving the base case, 1 mark for stating the inductive hypothesis and 2 marks for proving the inductive step.).

Solution

Let the number of elements in A is 3n then

a) T(3n) = 3T(n)+cn

or

T(n)=3T(n/3)+cn

Patitioning can be done in O(n) time and FindMin(A) can be solved by recursively calling algorithm three times. for that the term 3T(n/3)

By combining these two we get T(n)=3T(n/3)+cn;

b) T(n)=3T(n/3)+c n

This equation can be solved easily using Master\'s therorem. ie Using master\'s theorem we can prove that T(n)=nlog₃n.

c)Correctness of FindMin[A] by Induction

Base case : Consider an array of 1 element (which is the base case of the algorithm). Since the array has only one element and number of elements is less than 5 the algorithm returns that element as minimum. This proves the base case.

Inductive Hypothesis:
Assume that FindMin correctly finds min for k=1, 2, ..., 3n elements

Inductive Step:
Show that FindMin correctly works for k = 3n + 1 elements.
By the Inductive Hypothesis, since ceiling(k/3) < 3n:

x is a minimum of first k/3 elements in A1

y is a minimum of middle k/3 elements in A2

z is a minimum of last k/3 elements in A3

Then, by the correctness of the Findmin algorithm, FindMin returns the Minimum elements in the combined A1+ A2+A3 array. Furthermore, the resulting array contains all the elements of A (i.e., all k = 3n + 1 elements).

The algorithm terminates because we recursively reduce the size of each array by a factor of 3. Eventually each such array contains a single element, in which case the if statement causes Algorithm FindMin to return.

Hence the proof.