LFD Book Forum (http://book.caltech.edu/bookforum/index.php)
-   Homework 3 (http://book.caltech.edu/bookforum/forumdisplay.php?f=132)
-   -   Does dichotomy require growth function=2 for N=1? (http://book.caltech.edu/bookforum/showthread.php?t=929)

 Thomaseid 07-30-2012 10:02 PM

Does dichotomy require growth function=2 for N=1?

According to the definition of dichotomy, is it that at least for one point, there should be two ways to label this only point (+1 or -1), thus growth function=2 is required for N=1? Is this statement correct?

I am thinking that for iii) and iv) in Q5, these two growth function=1 for N=1, which excludes them from the space of growth functions (in addition to the polynomial or 2^N criteria). Please advice whether it is the right alternative way for solving Q5.

Thanks.

 yaser 07-30-2012 11:13 PM

Re: Does dichotomy require growth function=2 for N=1?

Quote:
 Originally Posted by Thomaseid (Post 3748) According to the definition of dichotomy, is it that at least for one point, there should be two ways to label this only point (+1 or -1), thus growth function=2 is required for N=1? Is this statement correct?
A dichotomy is a single pattern of 's on the points. It does not say anything about other patterns that may be valid on these points, so there is no implication on the value of the growth function.

 Thomaseid 07-31-2012 07:40 AM

Re: Does dichotomy require growth function=2 for N=1?

Thank you. Got it.

 All times are GMT -7. The time now is 01:12 PM.