does using divide & conquer improve the time complexity to find max and min in an array

Question

This was the question, I was asked in interview.

What is the best time complexity you can get to find a min and max of array?

I replied: O(n). Iterate through the array, keeping track of the max and min found so far. very simple and straightForward.

The interviewer asked can you improve it using divide and conquer. I said probably not. Then the conversation went on and finally I was asked to implement divide and conquer approach.

Here it is:

public class MinMaxInArray {
    public static int[] findMinMax(int[] array, int i, int j){
        // base cases
        int arrLen = j - i + 1;
        if (arrLen == 1)
            return new int[]{array[i], array[j]};    //j and i are the same

        if (arrLen == 2){
            int min = Math.min(array[i], array[j]);
            int max = Math.max(array[i], array[j])           
            return new int[]{min, max};
        }

        // actual divide and conquer        
        int mid = i + (j-i)/2;
        int[] leftMinMax = findMinMax(array, i, mid);
        int[] rightMinMax = findMinMax(array, mid+1, j);
        return new int[]{  Math.min(leftMinMax[0], rightMinMax[0]), Math.max(leftMinMax[1], rightMinMax[1])   };
    }

    public static void main(String[] args){
        int[] array = {20, 5, 7, 25, 30, 1, 9, 12};
        int[] minMax= findMinMax(array, 0, array.length - 1);           //minMax[0] = minimum value, minMax[1] = maximum value
        System.out.println("min = " + minMax[0] + ", max = " + minMax[1] );
    }

}

I am confident that this is still O(n) since all elements are compared. But the interviewer insisted that it is O(log n) and asked me to think about it. I thought quite a bit and I am convinced it is O(n). Just applying divide and conquer does not always reduce complexity if I am correct.

Please correct me if my understanding that this algorithm is still O(n).

Thank you

Uncouth

What is the connection between the question proper (iteration/divide&conquer) and the title (binary search)? – Goosefish

Answer 1

You are correct. Unless the array is sorted, you still have to examine every element in each half (and each quarter and each eighth as you recur).

The only way it can be O(log N) is if you can discard half the search space each recursion level (such as searching for a specific value in a sorted list) and the only way that can happen is if it's sorted.

But then, of course, the min and max operations become O(1) since you just grab the first and last element of the list, no need to search at all.

Now it may be that the examiner was suggesting divide-and-conquer in terms of farming off the different halves of each problem level to different execution engines so they could run in parallel. That's the only other way I could see it giving you O(log N) but I see no real evidence based on what's posted that suggests this was the case, and I think it would need quite a few engines.

Gluten

The examiner might also have been thinking of very large data arrays that could not fit in memory (say on a limited memory device) then divide-and-conquer may make sense to avoid too much disk swapping. – Anthraquinone

Answer 2

It's true that using divide and conquer the time complexity for finding min and max is O(n).

But using divide and conquer the number of comparisons can be reduced to a great extent which indeed reduces time if the data is huge.

So divide and conquer approach does 3/2n -2 comparisons if n is a power of 2. And it does more than 3/2n -2 comparisons if n is not a power of 2.

Davidadavidde

Answer 3

I also agree "Find min,max using Divide & Conquer" is O(N)
because in "Divide and Conqer"
Divide --->Takes O(n), as it divide every segment into smaller one.
Conquer--->It could be any function, which is giving result. So Time complexity will be based on what conquer is doing. Like in Merge sort,Merging part takes log(n) time.

As in this case conquer is constant operation

Saury