Or, instead of "estimate the distribution" look at what conceptual properties of the instance the big-O cares about. And then derive big-O in terms of such pro

Or, instead of "estimate the distribution" look at what conceptual properties of the instance the big-O cares about. And then derive big-O in terms of such properties. See for example Tetris-LoadBalanced and Tetris-Reordered (on top of Tetris-LoadBalanced) for such works: https://arxiv.org/abs/1909.12102 https://arxiv.org/abs/1909.12102