Combinatorial characterization of exact learning with membership queries
To drive home the point of anonymous moose's example, consider the concept class that consists of functions that output 1 on only one point in {0,1}^n. The class is of size 2^n, and 2^n queries are needed in the worst-case. Take a look at worst-case Teaching Dimension (Goldman &amp; Schapire) which provides something similar to what you're looking for.