Exercise 2.2 (b)

[mauriciogruppi]

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 k-1} (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.

[htlin]

Your understanding seems very reasonable!

[subbupd]

m_H(N) = 2^k - This is perfect