Question

1a. Write pseudocode for a divide-and-conquer algorithm for finding the po- sition of the largest element in an array of n numbers.

5. Find the order of growth for solutions of the following recurrences.

a . T(n)=4T(n/2)+n,T(1)=1

b. T(n)=4T(n/2)+n2,T(1)=1

c. T(n)=4T(n/2)+n3,T(1)=1

Answer 1

1. For this problem, divide n conquer approach is used which famously know as TOURNAMENT METHOD, as most of the tournaments work like this.

First, Divide the array into two parts and compare the maximums and minimums of the two parts to get the maximum and the minimum of the full array.

Pseudo code goes like this.

Pair findMaxMin(array, array_size)
   if array_size = 1
      return element as both max and min
   else if arry_size = 2
      one comparison to determine max and min
      return that pair
   else    /* array_size  greater than 2 */
      recur for max and min of left half
      recur for max and min of right half
      1 comparison determines true max of the two candidates
      1 comparison determines true min of the two candidates
      return the pair of max and min

Now lets see the Time Complexity for this recurrence solution.

T(n) = T(Floor(n/2)) + T(Ceil(n/2)) + 2  
  T(2) = 1
  T(1) = 0

T(n) = 2T(n/2) + 2

Now as you can see, the solution is divided into two n/2 parts, which is nothing but divide and conquer.

2.this part can be solved easily via master's method.

HOPE I HELPED YOU.