#1




Exercise 2.2 (b)
The question is asking if there is a hypothesis set for which m_H(N) = N + 2^floor(N/2).
Theorem 2.4 states that m_H(N) <= sum{0 to k1} (N choose i) if k is a breakpoint. My understanding is that m_H(N) = 2^k or it is bounded by a polynomial. However, the given growth function m_H(N) = N + 2^floor(N/2) seems exponential because of 2^(N/2). Therefore my answer is NO, it does not make sense to look for such hypothesis set. Can someone clarify if this is correct? Edit: Indeed, it is possible to show that m_H(N) is not bounded by a polynomial. 
Thread Tools  
Display Modes  

