The complexity analysis says the storage requirement for the quadruplets is O(N^3). Wouldn't it rather be O(N^4)?

The problem seems to be an example of the discrete math formula X choose Y which is X! / (Y! * (X-Y)!). How many ways are there to pick a subset of Y elements from a set of population X?

In this case, we have N choose 4, which is N! / (4! * (N-4)!), which would give an expression of degree 4 in terms of N.