*ANSWER* q5
 

I see why i, ii, v are possible formulae for growth functions: We have seen examples in class.

But I don't see why iii and iv are not possible formulae for growth functions too, since both this quantities are smaller than the maximum i.e. 2^N (obviously in the case of iv for all N; and in the case of iii for N large - ok, I have not checked for all N).

Of course I would have a hard time coming up with a H that has exactly one of these growth functions, but why would that be impossible ? How can we be sure that no H can have that sort of growth function ?
I must have missed something..

Even if this type of consideration has little practical consequences, I would be interested to know.

Re: *answer* q5
 

Hi,

The reason is that we proved that the growth function is either identically or else it has to be bounded above by a polynomial. The two excluded cases are faster than any polynomial, but still short of .

Re: *ANSWER* q5
 

Argh !!
And you spent the whole of lecture 6 showing it !
And I followed..

Thank you for repeating !
It helps me learn..

By the way, I received the book and so far it is very good.

Re: *ANSWER* q5
 

Enjoy!

Re: *ANSWER* q5
 

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.

Re: *ANSWER* q5
 

Is the following solution also correct?

(iv) cannot be a growth function because for N=1, growth function according to the formula is 1. This means the number max number of dichotomies for all x is 1. Which implies for a given x the number of dichotomies is 1. Which implies for a given x, h(x) is the same for all h. Therefore for a given x & y, (h(x), h(y)) is the same for all h i.e. the cardinality of the dichotomy for any pair of values is 1 and hence the max. cardinality as we vary x & y is also 1. But substituting N = 2 in the formula gives the growth function = 2.

If the above is correct, then the same logic can be applied to determine (iii) also cannot be a growth function because, based on the formula, growth function for N=1 is 1 and for N=2, it is 2.

Re: *ANSWER* q5
 

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!