The growth function, also called the shatter coefficient or the shattering number, measures the richness of a set family or class of functions. It is especially used in the context of statistical learning theory, where it is used to study properties of statistical learning methods. The term 'growth function' was coined by Vapnik and Chervonenkis in their 1968 paper, where they also proved many of its properties. It is a basic concept in machine learning.

Let ${\displaystyle H}$ be a set family (a set of sets) and ${\displaystyle C}$ a set. Their intersection is defined as the following set-family:

The intersection-size (also called the index) of ${\displaystyle H}$ with respect to ${\displaystyle C}$ is ${\displaystyle |H\cap C|}$. If a set ${\displaystyle C_{m}}$ has ${\displaystyle m}$ elements then the index is at most ${\displaystyle 2^{m}}$. If the index is exactly 2^m then the set ${\displaystyle C}$ is said to be shattered by ${\displaystyle H}$, because ${\displaystyle H\cap C}$ contains all the subsets of ${\displaystyle C}$, i.e.:

The growth function measures the size of ${\displaystyle H\cap C}$ as a function of ${\displaystyle |C|}$. Formally:

Equivalently, let ${\displaystyle H}$ be a hypothesis-class (a set of binary functions) and ${\displaystyle C}$ a set with ${\displaystyle m}$ elements. The restriction of ${\displaystyle H}$ to ${\displaystyle C}$ is the set of binary functions on ${\displaystyle C}$ that can be derived from ${\displaystyle H}$:

The growth function measures the size of ${\displaystyle H_{C}}$ as a function of ${\displaystyle |C|}$:

1. The domain is the real line ${\displaystyle \mathbb {R} }$. The set-family ${\displaystyle H}$ contains all the half-lines (rays) from a given number to positive infinity, i.e., all sets of the form ${\displaystyle \{x>x_{0}\mid x\in \mathbb {R} \}}$ for some ${\displaystyle x_{0}\in \mathbb {R} }$. For any set ${\displaystyle C}$ of ${\displaystyle m}$ real numbers, the intersection ${\displaystyle H\cap C}$ contains ${\displaystyle m+1}$ sets: the empty set, the set containing the largest element of ${\displaystyle C}$, the set containing the two largest elements of ${\displaystyle C}$, and so on. Therefore: ${\displaystyle \operatorname {Growth} (H,m)=m+1}$. The same is true whether ${\displaystyle H}$ contains open half-lines, closed half-lines, or both.

2. The domain is the segment ${\displaystyle [0,1]}$. The set-family ${\displaystyle H}$ contains all the open sets. For any finite set ${\displaystyle C}$ of ${\displaystyle m}$ real numbers, the intersection ${\displaystyle H\cap C}$ contains all possible subsets of ${\displaystyle C}$. There are ${\displaystyle 2^{m}}$ such subsets, so ${\displaystyle \operatorname {Growth} (H,m)=2^{m}}$.