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?
$\begingroup$
$\endgroup$
2
-
$\begingroup$ Can we have more context on the example? What is $t$ here, and what is $n$? $\endgroup$– Ben GrossmannJun 30, 2014 at 23:09
-
2$\begingroup$ It means "asymptotic to". For future reference: Wikipedia's list of mathematical symbols. $\endgroup$– user856Jun 30, 2014 at 23:11
Add a comment
|
3 Answers
$\begingroup$
$\endgroup$
3
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$.
answered Jun 30, 2014 at 23:10
-
2$\begingroup$ Does $t$ depends on $n$? Because this limit seems to tend to $0$ for every constant $t \in \mathbb{R}$... $\endgroup$– SurbJun 30, 2014 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$– user122283Jun 30, 2014 at 23:16
-
1$\begingroup$ A.k.a. asymptotically equivalent. Thanks! $\endgroup$ Jun 30, 2014 at 23:18
$\begingroup$
$\endgroup$
5
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$– mudriJul 1, 2014 at 10:00
-
-
$\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$– apnortonJul 1, 2014 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$– mudriJul 1, 2014 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$ Jul 1, 2014 at 15:50
$\begingroup$
$\endgroup$
2
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$ Jul 1, 2014 at 7:33
-
1$\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$ Jul 2, 2014 at 14:49