While the number of subsets from a given set of \(n\)  points is \(2^n\) , its can be easily verified that the number of subsets that can be covered by a ball in \(\mathbb {R}^d\)  is roughly \(n^{O(d)}\) . The exponent \(O(d)\)  is called the VC-dimension of the family of balls in \(\mathbb {R}^d\) . The following definition is a simple generalization by [1]} for query spaces where the query set is a function and not a single set. The original definition of pseudo-dimension can be found e.g. in [2]} and is very similar to the definition of VC-dimension given by [3]} as well as many other similar measures for the complexity of a family of shapes.
