Quote:
Originally Posted by GB449
Is the following solution also correct?
(iii) cannot be a growth function. For N=1, the formula gives the growth function = 1. This means that the max number of dichotomies for a single point x, is 1 which implies for a given point x, the number of dichotomies is 1 which means h(x) is the same for all h. Now take any two points, x & y, (h(x), h(y)) will be the same for all h (because h(x) is the same for all h and h(y) is the same for all h). The number of dichotomies for a given x & y is therefore 1 so the max number of dichotomies as we vary x & y over X is also 1. But substituting N=2 in the formula gives 2.
If the above is true, the same logic can be applied to prove (iv) also cannot be a growth function.

Hi,
I am traveling and I only have primitive Internet access so I don't have the homework with me, but your argument sounds correct!