Write down the pseudocode for finding the minimum and maximum number from an array using Divide and Conquer. Derive the time complexity.

To find the minimum and maximum numbers in an array using the divide and conquer approach, we follow the strategy of dividing the array into smaller parts, solving them (finding min and max in each part), and then combining the results.

Pseudocode:

MinMax(arr, low, high)
1. If low == high:
      Return (arr[low], arr[low])   // Only one element, so both min and max are arr[low]

2. If low == high - 1:
      If arr[low] < arr[high]:
         Return (arr[low], arr[high])  // Two elements, compare them
      Else:
         Return (arr[high], arr[low])  // Two elements, compare them

3. Else:
      mid = (low + high) / 2
      (min1, max1) = MinMax(arr, low, mid)       // Find min, max in the left half
      (min2, max2) = MinMax(arr, mid+1, high)    // Find min, max in the right half
      Return (min(min1, min2), max(max1, max2))  // Combine the results

Explanation:

• If the array has only one element (low == high), that element is both the minimum and maximum.
• If there are two elements (low == high - 1), we compare them directly to determine the min and max.
• For larger arrays, we split the array into two halves, recursively find the min and max in each half, and then combine the results (taking the minimum of both minimums and the maximum of both maximums).

Time Complexity:

• In the worst case, the array is divided in half at each step, similar to merge sort.
• At each level of recursion, you make constant comparisons (combining results from the two halves).

Thus, the time complexity is:

O(n)

where n is the number of elements in the array.