# Meaning of math symbol ~

Segment of Example from Textbook:

$t=\dots$

More usefully, we have:

$t\sim n\log n$

I recall $\sim$ means "similarity" in geometry, same shape but not same size. How is it interpreted here?

• Can we have more context on the example? What is $t$ here, and what is $n$? Jun 30, 2014 at 23:09
• It means "asymptotic to". For future reference: Wikipedia's list of mathematical symbols.
– user856
Jun 30, 2014 at 23:11

In this context, it means that $$\lim_{n \to \infty}\frac{t}{n\log n}=1$$ That is, the quotient of both sides tends to $1$.

• Does $t$ depends on $n$? Because this limit seems to tend to $0$ for every constant $t \in \mathbb{R}$...
– Surb
Jun 30, 2014 at 23:15
• @Surb Yeah, you're right. I'm assuming, as I'm sure Daniel did, that $t$ is a function of $n$; more accurately, the OP should have written $t(n)$.
– user122283
Jun 30, 2014 at 23:16
• A.k.a. asymptotically equivalent. Thanks! Jun 30, 2014 at 23:18

The answer by Daniel Littlewood is absolutely correct in this context. To extend this to the general definition (not tied to the example at hand):

$$f(n) \sim g(n) \iff \lim_{n\to\infty} \left(\frac{f}{g}\right)(n) = 1$$

• How standard is the notation $\left(\frac f g\right)(n)$? I've only ever seen similar on Jakub Marian's blog, where it's used as part of a larger proposed system. Jul 1, 2014 at 10:00
• @JamesWood: the notation is standard in the sense widely understood, but unusual in the sense that it would not be typically used in this context. All $(f/g)$ means is the function defined pointwise by that ratio. Jul 1, 2014 at 10:50
• @JamesWood: What Stan said is right. However, I did think that the notation was a bit more standard - I was introduced to it in high school algebra at the same time as $(f+g)(x),(f-g)(x), (fg)(x)$ and $(f\circ g)(x)$. I'm finding that my algebra courses were different than most. ;) Jul 1, 2014 at 13:22
• @anorton It's weird that $f\circ g$ was introduced at the same time, since that's fundamentally different to the others. Didn't that make for confusion? Jul 1, 2014 at 14:14
• Thinking on it, though the notation is seems somewhat unusual in this context (at least in my experience; ymmv), it actually makes more sense. Limits are defined on functions, so something like $\lim\frac{f(n)}{g(n)}$ only makes sense by implicitly interpreting it as the limit of another function that's defined by pointwise division. Thus, one might as well make it explicit and write $\lim\left(\frac{f}{g}\right)(n)$. Jul 1, 2014 at 15:50

The symbol $\sim$ does not have a set meaning across all subjects, but it is almost always used to denote an equivalence relation: a relation that is reflexive, symmetric, and transitive.

Daniel Littlewood and anorton have already discussed what $\sim$ means in this instance, and we can verify that it is an equivalent relation between functions on $\Bbb R$.

Clearly for any function $f(n)$, we have that $f\sim f$ since $(f/f)(n)=1$ for all $n$ (with caveats about the zeros of $f$) and $\lim_{n\rightarrow\infty}1=1$.

Also if $f\sim g$ we then have that $g\sim f$. This follows from the fact that if $\lim_{n\rightarrow\infty}h(n)=1$ then $\lim_{n\rightarrow\infty}(1/h)(n)=1$. Applying this fact with $h=f/g$ we tell us that $\sim$ is symmetric.

Finally $\sim$ is transitive. This follows from the fact that if $\lim_{n\rightarrow\infty}h_1(n)=1$ and $\lim_{n\rightarrow\infty}h_2(n)=1$ then $\lim_{n\rightarrow\infty}(h_1h_2)(n)=1$. If we have that $f\sim g$ and $g\sim h$, apply the previous fact with $h_1=f/g$ and $h_2=g/h$, and you will get that $f\sim h$.

• This all looks fine but it has very little to do with the actual question. Jul 1, 2014 at 7:33
• @DavidRicherby I think it is a good thing to know how a particular meaning of the symbol fits into more general notation scheme. Jul 2, 2014 at 14:49