Yeah, not a bad idea; for any given problem, just scramble the labels and compare training time...

For my pet problem, there's quite different performance across classes. It would be tougher to do the comparison for a subset of classes, but could still probably design some kind of experiment.