Thread: HW 4 question3
View Single Post
Old 05-02-2012, 04:38 AM
elkka elkka is offline
Invited Guest
Join Date: Apr 2012
Posts: 57
Default Re: HW 4 question3

rohanag, the recursive bounds can easily be solved for \varepsilon, as 1. they are, essentially, quadratic equations, and 2. only one root is of interest, as \varepsilon>0. By solving the equations you get

(c) \varepsilon = \frac{1}{N}+\sqrt{\frac{1}{N^2}+\frac{1}{N}\ln{\frac{6m_\mathcal{H}(2N)}{\delta}}};

(d) \varepsilon = \frac{1}{N-2}+\sqrt{\frac{1}{(N-2)^2}+\frac{1}{2(N-2)}\ln{\frac{4m_\mathcal{H}(N^2)}{\delta}}}.
Reply With Quote