Union of k intervals — VC = 2k

Parent: examples Prereq: learning-theory — H, h, shattering.

Class of all k-band unions:

h(x) = + \iff x \in \textstyle\bigcup_{i=1}^{k} [a_i, b_i]

Count. Place 2k points and any labeling of them uses at most k maximal blocks of +; cover each +-block by one interval → realizable → shatters 2k → VC ≥ 2k. With 2k+1 points, the all-alternating labeling + − + − … + has k+1 separate +-blocks, needing k+1 intervals — impossible with k → no 2k+1 shatter → VC = 2k.

Each interval adds 2 to the VC. Let k → ∞ and you can label anything — the class becomes all-powerful, which is exactly where extra capacity stops helping (price-of-capacity).