CODEWITHSUNDEEP
algorithmdata-structurestime-complexitypowersetbinomial-theorem
javaq
javaq

Reputation: 131

Time Complexity of Finding All Possible Sub Array of an Array

As per the implementation of finding all possible sub-array from a given array as follows:

public class AllPossibleSubArray {

    public static void main(String[] args) {
        int[] arr = { 1, 2, 3 };
        List<List<Integer>> result = new ArrayList<>();

        for (int len = 0; len <= arr.length; len++) {
            if (len == 0) {
                result.add(new ArrayList<>());
            } else {
                for (int i = 0; i < arr.length - len + 1; i++) {
                    List<Integer> temp = new ArrayList<>();
                    for (int j = i; j < i + len; j++) {
                        temp.add(arr[j]);
                    }
                    result.add(temp);
                }
            }
        }

        result.forEach(System.out::println);
    }

As per my understanding that time complexity would be O(N^3) as there are three FOR loop.

But this problem is nothing but a power set i.e. finding all possible sub set from a given set. From various forum on web, time complexity of power set is 2^N (Binomial expansion) which is not same as O(N^3).

Am i missing some fundamental ?

Upvotes: 0

Views: 5387

Answers (2)

ibkoye
ibkoye

Reputation: 1

Like the post above said the optimal time complexity for getting all the possible subarrays in an array is O(N^2). I would also like to point out that by definition a subarray is contiguous. check the following link for the definition of a sub array. https://www.google.com/url?sa=t&source=web&rct=j&url=https://www.geeksforgeeks.org/subarraysubstring-vs-subsequence-and-programs-to-generate-them/amp/&ved=2ahUKEwiI8bOC9I76AhWRSvEDHWubCNAQFnoECAcQBQ&usg=AOvVaw1i1BkpzTxhLqu0mfVhCN87

Upvotes: 0

ruakh
ruakh

Reputation: 183466

But this problem is nothing but a power set i.e. finding all possible sub set from a given set.

That's not correct.

The code that you've posted only finds contiguous subarrays, meaning the list of all elements from one index to another index.

The power set, by contrast, would also include discontiguous subsequences, meaning ones that include two elements without including all of the elements between them.

I should also note that there are only O(n2) subarrays, and if you find a different way to represent them, you can find them in O(n2) time rather than O(n3) time as the code that you've posted does. (Specifically, you need a representation that allows you to reuse the shared parts of the lists, rather than having to copy all required elements every time.) By contrast, if you stick with the representation in your code where each list has a distinct copy, finding all subsets would actually require O(n·2n) time, rather than just O(2n) time.

Upvotes: 3

Related Questions