Back to course home
0% completed
Vote For New Content
why does creating subarrays take O(N^2) time in the worst case?
samah
Sep 7, 2023
why does creating subarrays take O(N^2) time in the worst case?
0
0
Comments
Comments
S
Sri Harsha Chilakapati2 years ago
The worst case is the scenario where the target is more than the product of all the elements in the first array combined.
Hence, if the array is
[ 1, 2, 3, 4, 5, 6 ]
and the target is 1500, then the pairs will be every possible combination of the numbers. So O(N) f...
E
Ejike Nwude2 years ago
I believe this might be due to the fact that we are inserting each sub-array at the beginning of the array to maintain the order of the elements:
subarray.add(0, arr[i]);
This operation takes O(N) time since we need to shift all the elements over for...