CODEWITHSUNDEEP
arraysalgorithmtime-complexitydivide-and-conquer
Laniaventia
Laniaventia

Reputation: 45

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

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!

Upvotes: 3

Views: 2076

Answers (3)

Ice
Ice

Reputation: 74

Keep in mind that the space of the solutions for finding the max element in an unsorted array of N elements is N itself. The problem is lower bounded lineary by the dimension of the input, Ω(n), so finding something better than that is impossible.

Upvotes: 0

JuniorCompressor
JuniorCompressor

Reputation: 20015

When you have one element your algorithm has cost 1 (the cost to return the only element)

T(1) = 1

Otherwise, it's two recursive calls, that split the input to half, plus a constant number of operations:

T(n) = T(floor(n / 2)) + T(ceil(n / 2)) + c

Using the master theorem we can find the following asymptotic solution:

T(n) = O(n)

e.g. a linear algorithm. So asymptotically, the iterative version of the algorithm and the recursive one need the same time.

Upvotes: 4

Paul Hankin
Paul Hankin

Reputation: 58261

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.

Upvotes: 5

Related Questions