LFD Book Forum - View Single Post

vsthakur · #8 08-29-2012, 03:10 AM

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

and $d_{vc}$ .

Also, we know that if $N \le d_{vc}$ then

is an increasing function whose value is

. But, if $N > d_{vc}$ , then we can only say that

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,

Vishwajeet.