What would be the space complexity of an ArrayList of ArrayLists in Java?

Question

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?

Answer 1

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²).