Algorithm Divide and Conquer

Finding minimum and maximum

Finding minimum and maximum using divide and conquer

Finding minimum and maximum

Problem statement

Input: Given an array of n elements.
Output: Return maximum and minimum element.

Approach 1: without using divide and conquer

Example:

This problem can be solved by initializing max and min element as the first and running a for loop
from second index of the array comparing each element with the initialized value. If the value at current index is less than min, update min else if the value is greater than max, update max.
Algorithm:

Time Complexity:

In best case: number of comparisons will be n-1, as the first statement will evaluate to true always.
In worst case: number of comparisons will be 2(n-1), as both comparisons will be done.
In average case: number of comparisons will be between 2(n-1) and n-1.
Time complexity can be given by TC=O(1)+2(n-1)
Therefore ,time complexity is O(n)

Space complexity:

Approach 2: using divide and conquer

By using divide and conquer, we use a recursive relation which breaks the problem from middle element into two equal parts.We solve the problem recursively. Note: Each recursive function uses stack.
Algorithm:

Time complexity is determined for else part of the code. The initial conditions in if are called termination conditions and do not determine complexity. Referring to above code:
Time complexity :

Space complexity:

Summary
Finding minimum and maximum
Article Name
Finding minimum and maximum
Description
Finding minimum and maximum-Problem statement is Input: Given an array of n elements. Output: Return maximum and minimum element. We can solve this problem by using divide and conquer in O(n) time and logn extra space.
Author
Publisher Name
Scanfcode
Publisher Logo