Textbook
With $g(n)>0$ for sufficiently large natural $n$, asymptotic equivalence $f(n)\sim g(n)$ means $\lim_{n\to\infty}f(n)/g(n)=1$. The function $f$ is also eventually positive. Equivalently, $(f(n)-g(n))/g(n)\to0$.
For $f(n)=n+7$ and $g(n)=n$, the ratio is $1+7/n$, so $n+7\sim n$. The absolute difference remains 7, but vanishes relative to the growing scale. Equality at finite inputs is not required.
The function $3n+7$ is not equivalent to $n$: its ratio tends to 3. Both have order $\Theta(n)$, so equivalence is stronger than equal growth order. A constant multiplier matters here.
This notation differs from $X\sim D$ in probability, where the same sign names a distribution. Automatic substitution of equivalents into subtraction of close quantities can fail: leading parts can cancel, leaving the discarded difference in control of the answer.
The definition demands a check for every relative tolerance $\varepsilon>0$: beyond some $n_0$, the inequality $|f(n)/g(n)-1|<\varepsilon$ must hold. The threshold may depend on that tolerance. For $f(n)=n+7$, taking $n>7/\varepsilon$ suffices. Several close ratios cannot establish equivalence on their own; the whole remaining tail must stay controlled for each arbitrarily small positive tolerance.
Definitions and notation: Mathematics for Computer Science.
Related concepts: Limits of sequences, Big Theta: a tight growth order.
In plain language
A difference of seven units matters beside ten and becomes almost invisible beside a million. Asymptotic equivalence requires the relative discrepancy to tend to zero as the scale grows. If one amount stays three times the other, the shared label “linear growth” does not produce that closeness. The seven units themselves have not vanished: asymptotics explains their relative share but offers no discount on the final invoice.
Example
The constructed example compares the functions $n+7$ and $3n+7$ with $n$. The comparison tracks ratios rather than just their growing values.
Asymptotic equivalence
Input 10
The ratios are 1.7 and 3.7.
Step 1 of 4: Input 10
Read all steps
Input 10
The ratios are 1.7 and 3.7.
- n; (n+7)/n; (3n+7)/n
- 101.7current3.7current
Input 100
The term 7/n shrinks to 0.07 in both ratios.
- n; ratios
- 1001.07included3.07excluded
Input 1000
The first ratio is near 1; the second is near 3.
- n; ratios
- 10001.007included3.007excluded
Limits
Only the first comparison gives asymptotic equivalence to n.
- Ratio limits
- 1included3excluded
In the first column, the ratio differs from one by 0.7, then 0.07, then 0.007: multiplying the input by ten divides the discrepancy by ten. In the other column, the same extra term vanishes but a factor of 3 remains. A million-row table is unnecessary. The formulas $1+7/n$ and $3+7/n$ already identify different limits throughout the eventual tail.
Equivalence requires a ratio limit of 1. Equal order allows multipliers that change the answer here.