LFD Book Forum (http://book.caltech.edu/bookforum/index.php)
-   Homework 3 (http://book.caltech.edu/bookforum/forumdisplay.php?f=132)

 OlivierB 04-21-2013 02:55 PM

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.

 yaser 04-21-2013 03:50 PM

Quote:
 Originally Posted by OlivierB (Post 10539) 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 ?
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 .

 OlivierB 04-21-2013 05:58 PM

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.

 yaser 04-21-2013 09:06 PM

Quote:
 Originally Posted by OlivierB (Post 10542) 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.
Enjoy!

 GB449 09-07-2013 03:59 PM

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.

 GB449 09-07-2013 04:17 PM

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.

 yaser 09-09-2013 05:09 PM