View Single Post
Old 08-29-2012, 03:10 AM
vsthakur vsthakur is offline
Join Date: Jun 2012
Posts: 14
Default Problem 2.10

To prove : m_H(2N) \le m_H(N)^2

As this is a generic statement, it has to apply to every growth function. But all we know about the growth functions (in general) is their bound, in terms of N and d_{vc}.

Also, we know that if N \le d_{vc} then m_H(N) is an increasing function whose value is 2^N. But, if N > d_{vc}, then we can only say that m_H(N) is non-decreasing and is bounded by N^{d_{vc}} + 1.

I guess my question is that how can we prove the generic statement above. Kindly shed some light on the proof strategy.

Thank you,

Reply With Quote