We formalize the notion of size generalization in the context of data-driven algorithm selection and prove size generalization guarantees for three clustering algorithms and two max-cut algorithms.