5
$\begingroup$

What does "hold uniformly" mean in the statement of Theorem 1.7 in A Faster Subquadratic Algorithm for Finding Outlier Correlations? Here's the theorem text ("hold uniformly" is in the last line):

enter image description here

$\endgroup$
1
  • 1
    $\begingroup$ I don't find it very clear in this context. Possibly what they mean is that the constants and log factors hidden in the $\tilde{O}$ do not change even if $n,\tau,\rho$ change. $\endgroup$
    – usul
    Jul 19, 2018 at 17:16

1 Answer 1

5
$\begingroup$

We say a bound on a family of objects holds uniformity if there is a single bound that applies to all objects in the family, as opposed to a bound that is dependent upon the parameter that determines which element of the family is under discussion.

For example, $f_n(x)= \sin(nx)$ is uniformly bounded by $1$, while $g_n(x)=n\cos(nx)$ is not. In fact, $g_n$ isn’t uniformly bounded by anything, as any bound on it needs to depend on $n$.

$\endgroup$
4
  • 2
    $\begingroup$ Not a typo, just subject-verb agreement. "The bounds hold" vs "the bound holds". (Hint: "running time" is a noun adjunct, not the subject.) $\endgroup$ Jul 19, 2018 at 6:08
  • $\begingroup$ Thanks, that's what I thought but I wanted to double check $\endgroup$ Jul 19, 2018 at 12:31
  • $\begingroup$ I don't think there's a typo. There are two bounds given, one in (2) and the other in the third line of text. So I think bounds plural is correct. $\endgroup$ Jul 26, 2018 at 18:01
  • 1
    $\begingroup$ @ElliotGorokhovsky Oh I see. You’re likely right. $\endgroup$ Jul 26, 2018 at 18:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.