Big-O time complexity of 4sum problem. Brute force approach

Question

I am doing this problem called 4sum. Link to problem.

Given an array of n numbers and an integer(this is the target element). Calculate the total number of quads (collection of 4 distinct numbers chosen from these n numbers) are there for which the sum of quad elements will add up to the target element.

I wrote this code for brute force approach. According to me the big-o time complexity comes out to be --- n^4 log (n^4). I have given the reason below. Although the complexity should be n^4 only. Please help me understand what am i missing.

set>s;
for (int i = 0; i < n; i++) {
    for (int j = i + 1; j < n; j++) {
        for (int k = j + 1; k < n; k++) {
            for(int l = k + 1; l < n; l++) {
                if (a[i]+a[j]+a[k]+a[l]==target) {
                    s.insert({a[i], a[j], a[k], a[l]});
                }
            }
        }
    }
}

Logic is to generate all possible quads (with distinct elements), then for each quad check whether the sum of quad elements is equal to the target or not. If yes, then insert the quad in the set.

Now, we cannot know how many quads will match this condition because this solely depends on input. But to get the upper bound we assume that every quad that we check satisfies the condition. Hence, there are a total of N^4 insertions in the set. For N^4 insertions --- complexity is N^4 log(N^4).

user_5538420 · Answer

  if (a[i]+a[j]+a[k]+a[l]==target) {
    s.insert({a[i], a[j], a[k], a[l]});
  }

This gets executed O(N^4) times, indeed.

to get the upper bound we assume that every quad that we check satisfies the condition.

Correct.

For N^4 insertions --- complexity is N^4 log(N^4).

Not so, because N^4 insertions do not necessarily result in a set with N^4 elements.

The cost of an insertion is O(log(s.size()). But s.size() is upper-bound by the number of distinct ways K in which target can be expressed as a sum of 4 integers in a given range, so the worst case cost is O(log(K)). While K can be a large number, it does not depend on N, so as far as the complexity in N is concerned, this counts as constant time O(1), and therefore the overall complexity is still O(N^4)·O(1) = O(N^4).

[ EDIT ] Regarding @MysteriousUser's suggestion to use std::unordered_set instead of std::set, that would change the O(1) constant of the loop body to a better one, indeed, but would not change the overall complexity, which would still be O(N^4).

The other option which would in fact increase the complexity to O(N^4 log(N)) as proposed by the OP would be std::multi_set, since in that case each insertion would result in a size increase of the multiset.

Big-O time complexity of 4sum problem. Brute force approach

1 Answers