0

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.

Nadia Noormohamed
  • 19
  • 1
  • 6
  • In your case D&C can be more efficient if, as you already thought, you divide the array in chunks and set **several threads**, one for each chunck. Gather the results of the threads and repeat with this size-reduced array. – Ripi2 Sep 13 '17 at 21:41
  • 1
    You need to check *each* number in array so it will be O(n) – FelixEnescu Sep 13 '17 at 21:43
  • blueCat I measure the complexity using the comparison operation, and in the worst case that would amount to n - 1? – Nadia Noormohamed Sep 13 '17 at 21:45
  • O(n) or O(n-1) doesn't make any real difference; they both mean that the complexity is linear, i.e. if you double the input, it'll double the number of steps that need to be taken to process that input. Finding the maximum of an unordered list will never go below O(n) complexity, but you can of course use D&C to throw more processors at it, as Ripi2 mentioned, and improve the speed in real terms. – m69's been on strike for years Sep 13 '17 at 21:49
  • The complexity would be O(n) whether it's n-1 or n+1, since O(n), O(n+1) and O(n-1) (and O(n/2) FWIW) **are all literally the same thing**. [What is a plain English explanation of “Big O” notation?](https://stackoverflow.com/questions/487258/what-is-a-plain-english-explanation-of-big-o-notation) You can, however, look at the actual number of comparisons (which will be closer to 2n for naive implementation of finding the min and max), for example, if you want (and ignore complexity). – Bernhard Barker Sep 14 '17 at 01:31
  • One way to use divide-and-conquer is to use a divide-and-conquer algorithm such as Quicksort to sort the array, then take the first (min) or last (max) element directly. – Bob Jarvis - Слава Україні Sep 20 '17 at 11:37

2 Answers2

0

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.

William Kinaan
  • 28,059
  • 20
  • 85
  • 118
0

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.

Marco
  • 2,007
  • 17
  • 28