What is the time complexity of the Divide and Conquer algorithm for finding…

For a divide-and-conquer algorithm that splits a problem of size n into two subproblems of size n/2 and combines their results in constant time, the running time follows the recurrence T(n) = 2T(n/2) + O(1). By the Master theorem (a = 2, b = 2, f(n) = O(1)), this is Case 1 — the recursive branching term equates to n (since log₂2 = 1) and dominates a combine step that is asymptotically smaller — so the overall complexity is Θ(n), i.e. linear in the input size.

Applying this to the given problem:

1. Pair up the n elements into n/2 pairs as the base case (taking n as a power of two for a clean count — an odd/uneven n only needs two extra comparisons to fold in the one leftover element, and does not change the growth rate): within each pair, exactly one comparison finds the local maximum and local minimum — this costs n/2 comparisons in total.

2. Recursively combine two adjacent results into one with exactly two comparisons: one comparing the two local maxima to get the new maximum, one comparing the two local minima to get the new minimum — this combine step costs O(1) per merge, independent of subproblem size.

3. A binary recursion tree over n/2 base pairs has (n/2 − 1) combine (internal) nodes, so the combine phase costs 2 × (n/2 − 1) = n − 2 comparisons in total.

4. Total comparisons = n/2 (base pairs) + (n − 2) (combines) = 3n/2 − 2 for this even/power-of-two n — fewer than a naive linear scan’s 2n − 2 comparisons, though the growth rate stays linear either way.

5. Formally this is the recurrence T(n) = 2T(n/2) + O(1) with base case T(2) = O(1); by the Master theorem (Case 1) it again solves to T(n) = Θ(n), i.e. O(n) — this asymptotic result holds for any n, not only powers of two; only the exact constant in the comparison count depends on how the array splits.

Cross-check with the recursion-tree method (illustrated for n a power of two, so the tree is perfectly balanced): the recursion has log₂n levels, and the total number of internal (combine) nodes across the whole tree is proportional to n, each doing only O(1) work — summing this work across all levels totals Θ(n), the same result the Master theorem gives directly. For a non-power-of-two n the tree is not perfectly balanced, but the total combine work still sums to Θ(n) regardless of how the splits round, so the conclusion is unaffected. This also confirms the result is not affected by counting only the recursion depth, which would wrongly suggest a logarithmic time.