<p>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.</p>

<p>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$.</p>

CC BY-SA 4.0
2018-07-19T06:08:08.490Z
Not a typo, just subject-verb agreement. "The bounds hold" vs "the bound holds". (Hint: "running time" is a noun adjunct, not the subject.)
David Eppstein
CC BY-SA 4.0
2018-07-19T12:31:57.450Z
Thanks, that's what I thought but I wanted to double check
Elliot Gorokhovsky
CC BY-SA 4.0
2018-07-26T18:01:46.553Z
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.
Elliot Gorokhovsky
CC BY-SA 4.0
2018-07-26T18:02:41.457Z
@ElliotGorokhovsky Oh I see. You’re likely right.
Stella Biderman
CC BY-SA 4.0
2018-07-19T05:28:59.433Z
2018-07-26T18:03:23.823Z
2018-07-26T18:03:23.823Z
Stella Biderman
<p>What does "hold uniformly" mean in the statement of Theorem 1.7 in <a href="https://dl.acm.org/citation.cfm?id=3174804" rel="noreferrer">
A Faster Subquadratic Algorithm for Finding Outlier Correlations</a>? Here's the theorem text ("hold uniformly" is in the last line):</p>

<p><a href="https://i.sstatic.net/mXNBi.png" rel="noreferrer"><img src="https://i.sstatic.net/mXNBi.png" alt="enter image description here"></a></p>

CC BY-SA 4.0
2018-07-19T17:16:13.130Z
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.
usul
<cc.complexity-theory><ds.algorithms><asymptotics>
What does "hold uniformly" mean in the context of asymptotic analysis?
Elliot Gorokhovsky
# What does "hold uniformly" mean in the context of asymptotic analysis?

(Asked by: username_0 on 2018-07-19)

What does "hold uniformly" mean in the statement of Theorem 1.7 in [A Faster Subquadratic Algorithm for Finding Outlier Correlations](https://dl.acm.org/citation.cfm?id=3174804)? Here's the theorem text ("hold uniformly" is in the last line):

[![enter image description here](https://i.sstatic.net/mXNBi.png)](https://i.sstatic.net/mXNBi.png)

**Tags:** cc.complexity-theory, ds.algorithms, asymptotics
> **Comments:**
> **username_1**: 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.  

---

## 1 answers

### Answer by username_2 on 2018-07-19. Score: 5 | Accepted answer

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$.

> **Comments:**
> **username_3**: Not a typo, just subject-verb agreement. "The bounds hold" vs "the bound holds". (Hint: "running time" is a noun adjunct, not the subject.)  
> **username_0**: Thanks, that's what I thought but I wanted to double check  
> **username_0**: 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.  
> **username_2**: @ElliotGorokhovsky Oh I see. You’re likely right.  

---

