Thread: Problem 2.14(c)
View Single Post
  #11  
Old 11-11-2019, 04:19 AM
joseqft joseqft is offline
Junior Member
 
Join Date: Dec 2015
Posts: 1
Default Re: Problem 2.14(c)

Ive been struggling with this problem too. Essentialiy we have to prove that the second expression in the min expression

7(d_{VC}+K)\log_2(d_{VC}K).

is a valid \ell as explains magdon in

Quote:
Originally Posted by magdon View Post
Rather than solve the inequality in (b) to get this bound, you may rather just verify that this is a bound by showing that if \ell=7(d_{VC}+K)\log_2(d_{VC}K), then the inequality in (b) is satisfied, namely 2^\ell>2K\ell^{d_{VC}}.
this means that the inequality

(d_{VC}+K)^{7(d_{VC}+K)} > 2K\left[7(d_{VC}+K)\log_2(d_{VC}K)\right]^{d_{VC}} (1)

must be satisfied.

I have been finding upper bounds to the right hand side of (1), using the following tricks

d_{VC}+K \geq d_{VC}K if d_{VC}\geq 2 (the case d_{VC}= 1 must be proved apart).

\log_2(d_{VC}K) < d_{VC}K,

7 < 2^3 \leq K^3, because K \geq 2 (this is not the seven in the exponent) and

K + 1< K^2.

Then we arrive at an expression that can be compared easily with the left hand side of (1) proving that this inequality is valid.
Reply With Quote