I am new to machine learning and I am trying to resolve a homework problem. How do I determine the possible growth function $mH(N)$ for some hypothesis set? My choices are $1,2^N,2^\sqrt{N},N^2-N+2$ and none.
My research : I understand that the growth function counts the most dichotomies on any $N$ points and the growth function satisfies $mH(N) <= 2^N$.
Also, $mH(3) = 2^3 = 8, mH(4) = 14 < 2^4,$ Where $H$ is the perceptron.
From the definition of the VC dimension and the Sauer–Shelah lemma we know that the growth function can have only two types of behavior : polynomial (finite VC dim) or exponential (infinite VC dim) growth with respect to N.