Thread: *ANSWER* q5
View Single Post
  #7  
Old 09-09-2013, 05:09 PM
yaser's Avatar
yaser yaser is offline
Caltech
 
Join Date: Aug 2009
Location: Pasadena, California, USA
Posts: 1,477
Default Re: *ANSWER* q5

Quote:
Originally Posted by GB449 View Post
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
Reply With Quote