Use the divide-and-conquer approach to write an algorithm that finds the largest item

Question

Use the divide-and-conquer approach to write an algorithm that finds the largest item
in a list of n items. Analyze your algorithm, and show the results in order notation

Answer 1

A divide-and-conquer algorithm for finding the maximum element in an array would split the array into two halves, solve each subproblem separately and return the maximum of the solutions to the two subproblems. The base case of the recursion would be when the subproblem has size 1, in which case the maximum is the element in the array. The recurrence for the running time is $T(n)=2T(n/2)+c$, which has solution $T(n)=\Theta(n)$ by the Master theorem. This is the same asymptotic running time as (but a constant factor larger than) linear search. Here's the pseudocode:

Function FindMax(A,p,r):  
#input: an array A[p..r]. Returns maximum value
if p=r then return A[p]  #base case of recursion
else: 
    q = (p+r)//2  #midpoint
    return max{FindMax(A,p,q), FindMax(A,q+1,r)}