Stack Exchange network consists of 183 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.
For what it's worth, some simulation data I have aligns well with $O(\sqrt{k/N})$. So, +1 for it being a pretty good guess, even if the argument is loose.
This looks great. Sorry if this is obvious, but when you take the union bound, I would have thought that was equivalent to multiplying the bound by ${k \choose 2}$, but you seem to have multiplied it by $k{k \choose 2}$. Where does the extra $k$ come from?
