Product of All Integers in a List PROD Input Aab list of int

Product of All Integers in a List (PROD) Input: A[a...b] list of integers. Output: pi^b_i=a A[i]. Let P(A[a...b]) represent the output of the PROD problem on input A[a...b] (by convention, the product of an empty list is defined to be 1). State two different divide-and-conquer self-reductions for the PROD problem. Give recursive algorithms based on your divide-and-conquer self-reductions to solve the PROD problem. What are the worst-case runtimes of the solutions you have obtained? (Just state the runtimes. You do not need to show your work.)

Solution

1. First way:

Reduce the problem by taking out each element and multiplying it by the product of the remaining elements in the list recursively. Do this till there is only one element left.

Second way:

Divide the array in half and call the product method on that and reduce it till there are just two elements left to be multiplied.

2. Algo for the first way:

def prod(arr):

    if arr.length == 1:

        return arr[0]

    else:

        return arr[0] * prod(arr[1:])

Algo for the second way:

def prod(arr):

    if arr.length == 2:

        return arr[0]*arr[1]

    else:

        return prod(arr[0:arr.length/2]) * prod(arr[arr.length/2:arr.length])

3. Running time for first method: O(n)

Running time for second method: O(log(n))