Time Analysis of a divide-and-conquer strategy fo find the max value in a array of size N

Question

I wrote this algorithm that finds the MAX number in a array of size N:

find_max (s,e,A){
if (s != e){
    mid = floor((e-s)/2) + s;
    a = find_max(s,mid,A);
    b = find_max(mid + 1, e,A);
    if (a > b){
        return a;
    }
    return b;
}
return A[s];

}

I'd like to know the time cost, the T(n) equation and if this algorithm is asymptotically larger, faster or equivalent to the non-divide-and-conquer strategy (comparison of each number sequentially).

I came up with some answers but I think they are not right.

Thank You!

Answer 1

The code performs n-1 comparisons, which is identical to the iterative version of the code, and is optimal (see "number of tennis matches in a tennis tournament puzzle").

The proof that your code uses n-1 comparisons follows from induction:

T(1) = 0

T(n) = 1 + T(floor(n/2)) + T(n - floor(n/2))
      = floor(n/2)-1 + n - floor(n/2)-1 + 1 (by induction)
      = n - 2 + 1
      = n - 1

Your recursive code uses O(log N) storage unlike the iterative version which uses O(1) storage.