What is the least time complexity algorithm to find all possible subsets of consecutive elements in an array?

user_13345674 0
Viewed 139

Suppose I have an array of {2, 5, 0}. I want to find all possible subsets of consecutive elements of this array. The result should be:

{2}, {5}, {0}, {2, 5}, {5, 0}, {2, 5, 0}

Note there is no {2, 0}.

I have found and thought of many solutions. However, most of them have a time complexity of O(n²) or O(2n). Is there an algorithm to solve this problem with a better time complexity, such as O(nlogn)?

subset pseudocode algorithm
1 Answers

No, it is not possible to do better than O(n²). The reason is that the number of elements in the expected output is O(n²).

Let i be the starting index of a sub array and j its ending index, then for a given i, there are n-i possible values for j:

i number of possibilities for j
0 n
1 n - 1
2 n - 2
.. ..
n - 1 1
n 0

The sum of the second column represents the total number of sub arrays in the output, i.e. 1+2+3+...n, which is n(n+1)/2, i.e. O(n²).

The above reasoning also describes a possible algorithm:

function slices(arr):
    n := size_of(arr)
    result := []
    for i := 0 to n-1:
        for j := i + 1 to n:
            sub := arr[i:j]  # a slice from arr starting at i and ending at j
            result.append(sub)
    return result

This pseudo code assumes that array indexes start at 0, and that the ending index is not itself included in a slice.

Also, it assumes that the slices are not making copies of the elements in the selected sub ranges (which would increase the complexity), but are mere references to ranges in the given array itself. Actual implementations are language dependent, but what always works is that the result is not represented as an actual collection of arrays, but as a collection of (i, j) tuples.

user_54598390
Related