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):
$\begingroup$
$\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$– usulJul 19, 2018 at 17:16
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
4
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$.
-
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