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.
