statement 2 is proven on page 2 of these <A HREF="https://www.cs.princeton.edu/courses/archive/fall13/cos521/lecnotes/lec11.pdf">lecture notes</A>     
<sub>note a typo at the top of that page, corrected at the bottom: the square root should cover both the $\log n$ in the numerator and the $n$ in the denominator</sub>