Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Segment of Example:

t = ...

More usefully, we have:

t ~ n*log(n)

Note: ~ means "similarity" like in geometry, same shape but not same size. How is it interpreted here?

Edit: yes, t depends on n

share|improve this question
    
Can we have more context on the example? What is $t$ here, and what is $n$? –  Omnomnomnom Jun 30 at 23:09
2  
It means "asymptotic to". For future reference: Wikipedia's list of mathematical symbols. –  Rahul Jun 30 at 23:11

3 Answers 3

up vote 12 down vote accepted

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

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

share|improve this answer
    
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. –  James Wood Jul 1 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. –  Stan Liou Jul 1 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. ;) –  anorton Jul 1 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? –  James Wood Jul 1 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)$. –  Stan Liou Jul 1 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$.

share|improve this answer
    
This all looks fine but it has very little to do with the actual question. –  David Richerby Jul 1 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. –  user87690 Jul 2 at 14:49

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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