I've thought about this and there's I think another reason coming from combinatorics. Consider a set of n cities. Being able to go from one city to another by

I've thought about this and there's I think another reason coming from combinatorics. Consider a set of n cities. Being able to go from one city to another by plane only requires n airports. However, to have a complete rail network, one needs n (n-1) / 2 tracks. Hence the complexity analysis: one solution is linear, the other one is quadratic.