0% completed
Why is the creating subarrays up to O(N^2)? From what I can tell the inner loop ...
Egzon Bislimi
Feb 9, 2022
Why is the creating subarrays up to O(N^2)? From what I can tell the inner loop for creating the subarrays is just traversing backwards at O(N) and adding arrays to the result.
0
0
Comments
Design Gurus4 years ago
You are right that the loop runs for O(N), but in each iteration, we are creating a new array from an existing array; which will take O(N). For java, this line will take O(N):
result.add(new ArrayList(tempList));
Let us know if we misunderstood your question.
gorgeous 3 years ago
Supposing that left=0 and right=3 at a particular iteration then we need to get all subsets within [0,3]. This would be 16 subsets. The deque and result seem to be generating just 4 of them(one per each index as we pass from 0 to 3). Please could u explain
gorgeous 3 years ago
*10 subsets, 4 of which end at 4, 3 ending at 3 , 2 at 2 ...
On this page