Problem 2.14(c) - Page 2

joseqft · #11 11-11-2019, 05:19 AM

I´ve 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

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

.

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

AlexS · #12 01-23-2020, 02:57 AM

Quote:

Originally Posted by joseqft

I´ve 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

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

.

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

Thread Tools
Show Printable Version Email this Page
Display Modes
Linear Mode Switch to Hybrid Mode Switch to Threaded Mode