Tell me more ×
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.
up vote 0 down vote favorite

Given an increasing function $f(x)$, I am quite often interested in finding another (hopefully simpler) function $g(x)$ such that $$\lim_{x \rightarrow \infty} \frac{f(x)}{g(x)} = 1 .$$

What is the correct mathematical notation/terminology for expressing the relationship between $f$ and $g$ in this context? It is certainly true that $f(x) \in \Theta(g(x))$ but this doesn't account for constant factors.

share|improve this question

2 Answers

up vote 1 down vote accepted

The usual notation is $f(x)\sim g(x)$ as $x\to\infty$; see this table of Bachmann-Landau notations.

share|improve this answer
Thanks. I thought I had seen that used without regard to constants but the table is clear, as you suggest. How would you say that in words? – user54551 Jan 1 at 16:49
@lip1: I’d say that $f$ and $g$ are asymptotically equal (as $x\to\infty$), $f$ is asymptotically equal to $g$ (as $x\to\infty$), etc. – Brian M. Scott Jan 1 at 16:51
Thanks. What is an "asymptotic approximation" in that case? – user54551 Jan 1 at 16:52
@lip1: I’ve not encountered the term before. My guess would be that $f$ is an asymptotic approximation to $g$ if $f\sim g$. – Brian M. Scott Jan 1 at 16:55
OK. Although I hate to accept answers too quicky... Your answer appears perfect. – user54551 Jan 1 at 16:56
show 1 more comment
up vote 0 down vote

If $f = \Theta(g)$, then $\frac{f}{g} \to c$ for some $c \in \mathbb{R}_{>0}$. Therefore, we may take the function $cg$, and get that $$\lim_{x \to \infty} \frac{f(x)}{cg(x)} = \frac{1}{c} \lim_{x \to \infty} \frac{f(x)}{g(x)} = \frac{1}{c} \cdot c = 1$$So this gives you a (hopefully) simpler function that has the same asymptotics as $f$.

And @Brian M Scott was spot on with his notation $f $~$ g$

share|improve this answer
I am not sure that definition of $\Theta$ is right. In particular, I think you only require that $f(x) \in O(g(x))$ and $f(x) \in \Omega(g(x))$ to have $f(x) \in \Theta(g(x))$ which does not imply that $f(x)/g(x) \rightarrow c$. – user54551 Jan 1 at 16:50
It's an equivalent definition. – andybenji Jan 1 at 17:23
A function $f(x) = (2+\sin(x))x$ is $\Theta(x)$ but $f(x)/x$ does not converge to a limit. – user54551 Jan 1 at 17:40

Your Answer

 
discard

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