This can be solved by simply traversing the array once and updating the max and min by comparing it with every element. Steps :
1. Initialize min and max with the value of the first element of the arra...read more

Sort the array so that the 0th element will be the minimum value of the array and the last element will be the maximum value present in out array.

O(1)

In the ...read more

Steps:

1. Create two variables maximum and minimum, and initialise with arr[0].
2. Run a loop from i = 1 to N-1 and do:
   1. If arr[i] > maximum, then make maximum = arr[i].
   2. Else If arr[i] < minimum, then ...read more

The idea is to use a divide and conquer approach in order to reduce the number of comparisons. We divide the array into two equal parts and find the maximum and minimum element of each part recursively. Then we compare the maximum and minimum of both parts in order to find the maximum and minimum element of the whole array.

Steps:

1. Create a data type that contains two integers as maximum and minimum. The first integer denotes the maximum value whereas the second one denotes the minimum value. Let’s denote the name of this variable as maxMin.
2. Implement a recursive function say findMaxMin(arr, 0, N-1).
3. Finally, return the sum of maximum and minimum.

pair<int, int> findMaxMin(arr, left, right):

1. If left == right, i.e. only one element is present in the array, then return {arr[left], arr[right]}.
2. If right == left + 1, i.e. only two elements are present in the array, then:
   1. If arr[left] > arr[right], then return {arr[left], arr[right]}.
   2. Else, return {arr[right], arr[left]}.
3. Create a mid variable and make mid = (left + right) / 2.
4. Create two more pairs of integers, say leftAns and rightAns in order to store the result of the left half and right half respectively.
5. Call the recursive function from left to mid for the leftAns and mid + 1 to right for the rightAns, i.e. leftAns = findMaxMin(arr, left, mid) and rightAns = findMaxMin(arr, mid+1, right).
6. Finally, return the maximum among the maximum of leftAns and rightAns and minimum among the minimum of leftAns and rightAns i.e. {max(leftAns.first, rightAns.first), min(leftAns.second, rightAns.second)}.

O(log N), where N is the size of the given array.

In the worst case, the number of recursive calls can go up to log N. Hence, the overall space complexity is O(log N).

O(N), where N is the size of the given array.

In the worst case, we will be traversing the whole array, hence the time complexity is O(N).

The number of comparisons can be calculated by the recurrence relation,

T(N) = T(floor(N / 2)) + T(Ceil(N / 2)) + 2

T(1) = 0, T(2) = 1

So, if N is a power of 2, we can represent T(N) = 2T(N / 2) + 2

So, by solving the above relation, we get T(N) = (3 * N) / 2 - 2

So, if N is a power of 2, then the total number of comparisons is (3 * N) / 2 - 2 and if it is not a power of 2, then it will take a few more comparisons, but the difference is not so significant.