I have a method that returns List<List<Integer>> in Java. What would be the Space Complexity of this data structure? Would it be O(N*M), due to nested ArrayLists inside an ArrayList? Or something else?

CodePudding user response：

You have the right idea, but may need to refine it a bit.

For the "outer" ArrayList, the space complexity is O(n), n being the number of elements in it.
Following your instinct, you should multiply that by the space complexity of the inner ArrayLists, which is also their respective size.
However, without any additional information or constraints, you shouldn't assume that the inner and outer ArrayLists have the same size, so in a more general sense you'd want to say that if the number of elements in the inner list is m, the total size complexity is O(m * n). If m=n (e.g. each index represents a location, and the the "cell" of the nested array represents the distance between the indexes of the outer and inner map), O(m * n) will indeed be reduced to O(n²).

CodePudding user response：

ArrayList are dynamic data structures and it increases its size by 50% more than the actual size(no of elements). So in real we can say it is taking N N/2 space. From the principle of complexity N is the highest degree so O(N). You have nested lists and inner list determines the space complexity. n elements in inner list and m inner lists are there then total complexity O(n*m)