Thread: Problem 2.14(c)
View Single Post
Old 01-23-2020, 02:57 AM
AlexS AlexS is offline
Junior Member
Join Date: Sep 2018
Posts: 7
Default Re: Problem 2.14(c)

Originally Posted by joseqft View Post
Ive been struggling with this problem too. Essentialiy we have to prove that the second expression in the min expression


is a valid \ell as explains magdon in

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 ASO expression that can be compared easily with the left hand side of (1) proving that this inequality is valid.
I think you will find mistake it is not hard
Reply With Quote