Time complexity of solution to the four sum problem?

user_5859885 0
Viewed 61

Given an array of integers, find all unique quartets summing up to a specified integer.

I will provide two different solutions below, I was just wondering which one was more efficient with respect to time complexity?

Solution 1:

def four_sum(arr, s): 
    n = len(arr)
    output = set()

    for i in range(n-2):       
        for j in range(i+1, n-1):
            seen = set()

            for k in range(j+1, n):
                target = s - arr[i] - arr[j] - arr[k]
                if target in seen:
                    output.add((arr[i], arr[j], arr[k], target))

                else:
                    seen.add(arr[k])

    return print('\n'.join(map(str, list(output))))

I know that this has time complexity of O(n^3).

Solution 2:

def four_sum2(arr, s):
    n = len(arr)

    seen = {} 
    for i in range(n-1):
        for j in range(i+1, n):
            if arr[i] + arr[j] in seen:
                seen[arr[i] + arr[j]].add((i, j)) 
            else:
                seen[arr[i] + arr[j]] = {(i, j)} 

    output = set()

    for key in seen:
        if s - key in seen:
            for (i, j) in seen[key]:
                for (p, q) in seen[s - key]:
                    sorted_index = tuple(sorted((arr[i], arr[j], arr[p], arr[q]))) 

                    if i not in (p, q) and j not in (p, q): 
                        output.add(sorted_index)

    return output

Now, the first block has a time complexity of O(n^2), but I'm not sure what the time complexity is on the second block?

time-complexity python-3.x python
1 Answers

TLDR: the complexity of this algorithm is O(n^4).

In the first part, a tuple is added in seen for all pair (i,j) where j>i. Thus the number of tuples in seen is about (n-1)*n/2 = O(n^2) as you guess.

The second part is a bit more complex. If we ignore the first condition of the nested loops (critical case), the two first loops can iterate over all possible tuples in seen. Thus the complexity is at least O(n^2). For the third loop, it is a bit tricky: it is hard to know the complexity without making any assumption on the input data. However, we can assume that there is theoretically a critical case where seen[s - key] contains O(n^2) tuples. In such a case, the overall algorithm would run in O(n^4)!

Is this theoretical critical case practical? Well, sadly yes. Indeed, take the input arr = [5, 5, ..., 5, 5] with s = 20 for example. The seen map will contains one key (10) associated to an array with (n-1)*n/2 = O(n^2) elements. In this case the two first loops of the second part will run in O(n^2) and third nested loop in O(n^2) too.

Thus the overall algorithm run in O(n^4).

However, note that in practice such case should be quite rare and the algorithm should run much faster on random inputs with many different numbers. The complexity can probably be improved to O(n^3) or even O(n^2) if this critical case is fixed (eg. by computing this pathological case separately).

user_129395570
Related