educative.io

Educative

About the space complexity storing all subarrays

The article asks “Can you try estimating how much space will be required for the output list?”
The answer it gives is O(N^2).

The average length of a subarray is O(N), and there’re O(N^2) subarrays in total, so the space complexity for storing all subarrays should be O(N^3).

Please correct me if I’m wrong.

1 Like

I agree, the space complexity is O(N^3). The article is only counting the subarrays without taking their length into account.

1 Like

Yes, I had the same concern. The space complexity should be O(N^3)