#7
09-09-2013, 05:09 PM
 yaser Caltech Join Date: Aug 2009 Location: Pasadena, California, USA Posts: 1,477

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!
__________________
Where everyone thinks alike, no one thinks very much