Asymptotic Estimates

Often times we can't just compute lim_{n ⟶ ∞} a_n because it turns out to be ∞. We introduce some notation for comparing the orders of magnitude of two sequences. This will also be useful in comparing the relative growth rates of sequences. For instance it might be said that the function n grows faster than log n but slower than n². Let (a_n) and (b_n) be any sequences in ℝ.

Definition 2.3.1. Let {a_n} convergent to L for n ⟶ ∞. If there are K > 0 and n₀ ∈ ℕ such that

One reads the statement “a_n = O(b_n)” as “(a_n) is big-oh of (b_n)”. Writing a_n = O(b_n) means, in rough terms, that the sequence a_n grows no faster than the test sequence b_n. If a_n = 2n + 50 then we see that a_n = O(n²). The role of K in the definition is to allow us to no have to distinguish between test sequences e.g. n² and 2n², since 2n² = O(n²).

If b_n = 1 for all large n, then we simply write a_n = O(1), and this means that the sequence (a_n) is bounded.

Definition 2.3.2 If for every ε > 0, there is n₀ ∈ ℕ such that

One reads the statement “a_n = o(b_n) as “(a_n) is little-oh of (b_n)”. If b_n ≠ 0 for all large n, then a_n = o(b_n) means that lim_n→∞ (a_n/b_n) exists and is zero. In particular, if b_n = 1 for all large n, then we simply write a_n = o(1), and this means that a_n → 0. For example,

Definition 2.3.3. Suppose b_n ≠ 0 for all large n. We say that {a_n} is asymptotically equivalent to {b_n} and write a_n ∼ b_n if

For example,

Finally, suppose {b_n} is monotonic and b_n > 0 for all large n. We say that {a_n} and {b_n} have the same growth rate if a_n ∼ ℓb_n for some ℓ ∈ R with ℓ ≠ 0. In case a_n = o(b_n), then we say that the growth rate of (a_n) is less than the growth rate of (b_n). On the other hand, if a_n = O(b_n), then we say that the growth rate of {a_n} is at most the growth rate of {b_n}.

The notations O( ) and o( ) stand for collections of functions. It is unfortunate that the symbol "=" is used here since, there is no actual equality.

• O(b_n): the set of sequences that grow no more rapidly than a positive multiple (K) of b_n;

• o(b_n): the set of sequences that grow less rapidly than a positive multiple (K) of b_n.

We'll show later that

$$\begin{array}{rlrl}& \underset{n\to \mathrm{\infty }}{lim}\frac{{\log }_{a}n}{n^a}=0& & \\ & & & \mathrm{\forall }a>0,a>1\\ & \underset{n\to \mathrm{\infty }}{lim}\frac{n^a}{a^n}=0& & \end{array}$$

Example 2.3.4.

$$\underset{n\to \mathrm{\infty }}{lim}\frac{3n^3+5n+1}{7(n+1{)}^3}=\frac{[\mathrm{\infty }]}{[\mathrm{\infty }]}$$ $$\frac{3n^3+5n+1}{7(n+1{)}^3}\sim \frac{3n^3}{7n^3}=\frac{3}{7}$$

hence the sequence tends to 3/7.  ■

Example 2.3.5.

$$\underset{n\to \mathrm{\infty }}{lim}\frac{3^n+n}{3^{n+1}}=\frac{[\mathrm{\infty }]}{[\mathrm{\infty }]}$$ $$\frac{3^n+n}{3^{n+1}}\sim \frac{3^n}{3^{n+1}}=\frac{1}{3}$$

This because 3ⁿ + n = 3ⁿ (1 + n/3ⁿ) ~ 3ⁿ. And n/3ⁿ ⟶ 0.  ■

Example 2.3.6. lim_{n ⟶ ∞} n^1/n = [∞⁰].

n^1/n = e^{log n1/n} = e^{log n/n} ⟶ e⁰ = 1.

Where we used the fact that lim_{n ⟶ ∞} log n/n ⟶ 0.  ■

«Epoxides Index Sulfides»