Increasing algorithm efficiency using divide and conquer paradigm

Question

I want to find the minimum and maximum integer within an array. My relatively inefficient method is to consider the first integer to by the max\min. I then compare this with the other integers and if a greater/smaller integer is compared with the current minimum or maximum integer then that is replaced. This takes place until the end of the array. From what I have worked out the complexity (based on the worst case) is n -1 (n is the size of the array). My question is how could I use the divide and conquer paradigm to make this more efficient? I have tried by dividing the array into two parts and then doing the same algorithm as above to both divisions although that just makes everything less efficient? From my calculations the complexity becomes n + 1.

Answer 1

In order to identify the maximum of n elements an algorithm has to gain enough information from the comparisons. Assuming the maximum is array[i], you have to compare array[i] against array[0], ... array[i-1], array[i+1], ... array[n-1] in order to prove array[i] is the maximum. So the minimum number of comparisons required is n - 1 comparisons in order to find the maximum. Why? Because there are n elements in the array and the algorithm have to make enough information from the comparisons in order to find the maximum.

---

Example code in Python

# Divide-and-Conquer find max of alist
def dc_max(alist, start, end): # first call with start=0, end=len(alist)
    if end - start == 1: # base case: list of 1 element
        return alist[start]
    mid = (start + end) // 2
    x = dc_max(alist, start, mid)
    y = dc_max(alist, mid, end)
    if x > y:
        return x
    return y

# Iterative find max of alist
def it_max(alist):
    current = alist[0]
    for i in range(1, len(alist)):
        if i > current:
            current = i
    return current

Both algorithms do exactly n - 1 comparisons and are in-place, so they both have Θ(n) time complexity and O(1) spatial complexity.

---

Performance now depends on your system. See Is recursion ever faster than looping?

In my case, finding the maximum of a list of 2**20 numbers took 657ms with the recursive method and 111ms with the iterative one.

Answer 2

I will consider that you're using one thread

If the array is not sorted, the complexity will always be O(n). However, in my opinion, you should check that do you just need the max number? or the second max as well, and the third max as well ..

If that's the case, you'd better build a max heap (min heap for the counterpart case), which takes O(nlogn) time, and then just check the peek of the heap.