Sauer-Shelah Bound

Problem

Return the Sauer-Shelah bound on the growth function of a class with VC dimension d:

m(n) <= sum_{i=0}^{d} C(n, i)

When d >= n the bound is the full 2^n labelings.

Hint

For fixed d the bound grows only polynomially in n.

case 1

in: [10,2]

expected: 56

case 2

in: [5,1]

expected: 6

case 3

in: [4,4]

expected: 16

case 4

in: [3,0]

expected: 1

case 5

in: [7,3]

expected: 64

Starter codePython

import math
def sauer_shelah_bound(n, d):
    # Your code here
    pass

5 test cases · run your code against them in the editor