Question

design a divide & conquer alogrithm that requires 2 recursive calls for array size greater than 2. the algorithm should receive an array of ints and output the product of the array. provide the reccurence equation and the big-oh analysis/tightest bound. and show the run-time if input to the algorithm passed the entire original array into the recursive call

Answer 1

The product of each elements from the array is the product of elements of left subarray and right subarray.

if the size of array is 2 then return product of both elements.

The algo is,

Product(x,start,end)

if start=end                           //if input size is 1

    return x[start]

if start+1=end                                // if size is 2

    return x[start]*x[end]                //return the product of each element

else return Product(x, start,(start+end-1)/2)*Product(x, (start+end+1)/2,end)       // product of left and right subarray

runtime analysis:

the algorithm breaks the problem of size n into 2 subproblems of size n/2 and takes constant time in doing so

so the recurrence is:

Solving it by recursively substituting T(n) we get

(assuming O(1) as 1, this will not change the running time since both are constants)

putting 2^k=n we get k=log(n)

Thus,

the first term on the right side is just O(n) since 2^logn=n and T(1)=1

the second term is a GP with logn terms and ratio=2 which sums to 2^logn-1 which is also O(n)

So T(n)=O(n)