View Single Post
Old 01-26-2013, 09:14 PM
yaser's Avatar
yaser yaser is offline
Join Date: Aug 2009
Location: Pasadena, California, USA
Posts: 1,478
Default Re: Q5, K dependency on N?

Originally Posted by ctallardc View Post
k (break point) is a fix value for a given type of hypothesis (problem) .
k do not depend of N, it is bound to N. Correct?
You are correct, but I am not sure what you mean by the last part. The bound k creates is on the growth function m_{\cal H}(N).

Also there is 2 option for growth function:

1-if there is not a break point then m_H(n) = 2^N
2-if there is break point m_H(n)<= \sum_{i=1}^{k-1} {{N}\choose{i}}, which is polynomial of degree k
Where everyone thinks alike, no one thinks very much
Reply With Quote