Segment of Example from Textbook:


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?

  • $\begingroup$ Can we have more context on the example? What is $t$ here, and what is $n$? $\endgroup$ – Omnomnomnom Jun 30 '14 at 23:09
  • 2
    $\begingroup$ It means "asymptotic to". For future reference: Wikipedia's list of mathematical symbols. $\endgroup$ – Rahul Jun 30 '14 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$.

  • 2
    $\begingroup$ Does $t$ depends on $n$? Because this limit seems to tend to $0$ for every constant $t \in \mathbb{R}$... $\endgroup$ – Surb Jun 30 '14 at 23:15
  • 1
    $\begingroup$ @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)$. $\endgroup$ – user122283 Jun 30 '14 at 23:16
  • 1
    $\begingroup$ A.k.a. asymptotically equivalent. Thanks! $\endgroup$ – A_for_ Abacus Jun 30 '14 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$$

  • $\begingroup$ 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. $\endgroup$ – James Wood Jul 1 '14 at 10:00
  • $\begingroup$ @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. $\endgroup$ – Stan Liou Jul 1 '14 at 10:50
  • $\begingroup$ @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. ;) $\endgroup$ – apnorton Jul 1 '14 at 13:22
  • $\begingroup$ @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? $\endgroup$ – James Wood Jul 1 '14 at 14:14
  • $\begingroup$ 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)$. $\endgroup$ – Stan Liou Jul 1 '14 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$.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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