Growth function




     Suppose there is a hypothesis set {h1, h2, h3}.

Each  of  them realizes one dichotomy, but the realizations of h1
and h3 are duplicated. Then the value of the growth  function  is
2.

The growth function is related to a hypothesis class.



     Determine  the  value  of the growth function of H. H is the
set of indicator functions of closed intervals.

Suppose points from left to right: p1, p2, ... pn.

In the case of at least one point is in the interval: i <= j. How
many pairs of i and j are valid? n + n‐1 + ... + 1.

In the case of none is in the interval: 1.

Total number of labeling: n*(n+1) / 2 + 1