Notes to a video lecture on http://www.unizor.com
Rate of Change: Big-O, Little-o
Consider two infinitely growing sequences
{n} and {n+1}.
Both are infinitely growing, the second one is always (for any order number n) greater than the first, so it is "bigger" in some sense.
But, if you compare the rate of their growth, it is, actually, the same. When one doubles in value, another almost doubles too and the difference gets proportionally smaller and smaller.
The difference between these sequences, as they grow, is always 1, but their values are getting larger and larger, so proportional difference is getting more and more negligible. For order number n=10 the difference of 1 represents 10% of the value, for n=1000 the difference of 1 represents only 0.1% of the value. This allows us to say that both sequence are growing at the same rate.
On the other hand, if you consider these infinitely growing sequences
{n} and {ln(n)},
you will soon see that proportional difference becomes larger and larger as n growth much faster than ln(n). For order number n=10 the first sequence has value 10, while the second, approximately, has 2.3 - 77% difference. For n=1000 the first sequence has value 1000, while the second, approximately, has 6.9 - more than 99% difference. And this proportional difference is growing. This allows us to say that the first sequence growth proportionally faster than the second. The rate of growth of the first sequence is greater than of the second.
Similar situation is with infinitesimals.
Consider two infinitesimal sequences
{1/n} and {10/n}.
Both are infinitesimal, though the first one is always smaller. Proportional difference between them is always 9/n, which represents 900% of the value of the first sequence. It does not change and, therefore, we can say that these two infinitesimals are diminishing with the same speed.
On the other hand, if you consider these infinitesimals
{1/n} and {1/ln(n)},
you will see that proportional difference is increasing as 1/n converges to zero much faster than 1/ln(n). Indeed, with order number n=10 the first sequence equals 0.1, while the second, approximately, is 0.4343 - more than 300% difference. For n=100 the first sequence is 0.01, while the second, approximately, is 0.2174 - more than 2000% difference. For n=1000 the first sequence is 0.001, while the second is 0.1448 - more than 14000% difference.
To address the relative rate of growth for infinitely growing sequences or relative rate of diminishing for infinitesimal sequences, there is a special notation called Big-O and Little-o.
Big-O means similar rate of change, while Little-o means "smaller" in terms of rate of change (slower growth for infinitely growing and faster diminishing for infinitesimals).
It should be noted that many sources differentiate between relative rates of change bounded from above (where it's called Big-O), from below (where it's called Ω) and from both sides (where it's called Θ).
For our purposes we will use only Big-O and assume that it refers to a relative rate of change bounded from both upper and lower sides. The definition below clarifies the exact meaning of this.
Thus, considering infinitely growing sequences, we can say that
n+1 = O(n) - to indicate the same rate of change or the same order of growing,
ln(n) = o(n) - to indicate that ln(n) is "smaller" in a sense of the rate of growing of ln(n) to infinity is slower than the rate of growing of n.
For infinitesimal sequences we can say that
10/n = O(1/n) - to indicate that both infinitesimals are diminishing to zero with the same speed, their order of diminishing is the same,
1/n = o(1/ln(n)) - to indicate that 1/n is "smaller" in a sense of the rate of diminishing to zero of 1/n is faster than the rate of diminishing to zero of 1/ln(n).
Let's now define Big-O and Little-o more rigorously.
Consider two sequences
{Xn} and {Yn}.
Definition of Little-o is based on the behavior of their ratio {Xn/Yn} (assuming Yn≠0).
If this ratio is an infinitesimal sequence, we say that
Xn = o(Yn)
Symbolically, the rate of change of Xn is o(Yn) if
∀ε>0 ∃N: n ≥ N ⇒ |Xn/Yn| ≤ ε
Definition of Big-O for two positive infinitely growing or infinitesimal sequences {Xn} and {Yn} is also based on the ratio {Xn/Yn}.
If, after certain order number, it is bounded from both sides by positive numbers, we say that these two sequences are of the same rate of change (or of the same order).
Symbolically, the rate of change of Xn is O(Yn) if
∃ A > 0, B > 0, N:
n ≥ N ⇒ A ≤ Xn/Yn ≤ B
Examples
1. Infinitely Growing - O()
Xn = 2n²+n−1; Yn = n²−1
Xn/Yn = (2n²+n−1)/(n²−1) =
= [(2n²−2)+(n+1)]/(n²−1) =
= 2+[(n+1)/(n²−1)] =
= 2+[1/(n−1)]
The last expression is, obviously, limited between A=2 and B=3 for n ≥ 2.
Therefore, Xn is O(Yn).
2. Infinitesimals - O()
Xn = 1/n; Yn = n/(n²−1)
Xn/Yn = (n²−1)/n² =
= 1−1/n²
The last expression is, obviously, limited between A=0.5 and B=1 for n ≥ 2.
Therefore, Xn is O(Yn).
3. Infinitely growing - o()
Xn = ln(n); Yn = n
Xn/Yn = ln(n)/n = ln(n1/n)
Expression n1/n converges to 1.
Here is a proof (with a help of a trick).
Let Zn=n1/n−1.
Obviously, Zn ≥ 0.
Consider an expression
(1+Zn)n.
On one hand, it is equal to
(1+n1/n−1)n = n.
On the other hand, let's use Newton's binomial for it:
(1+Zn)n = Σi∈[0,n]CniZni
Replacing the left side with n and leaving only one member of the sum on the right - the one with Zn2 - we come up with the following inequality:
n ≥ Cn2Zn2
Since Cn2 = n(n−1)/2,
n ≥ Zn2n(n−1)/2 or
Zn2 ≤ 2/(n−1),
which proves that Zn is an infinitesimal variable and, therefore, n1/n→1.
Therefore, ln(n1/n) is converging to 0.
Therefore, Xn is o(Yn).
4. Infinitesimals - o()
Xn = 1/2n; Yn = 1/n
Xn/Yn = n/2n;
The expression n/2n is converging to zero.
Here is a proof.
Use Newton's binomial for identity
2n = Σi∈[0,n]Cni
Using only one member of the sum on the right, we come up with an inequality
2n ≥ n(n−1)/2
from which follows
n/2n ≤ 2/(n−1).
Therefore, n/2n is an infinitesimal.
Therefore, Xn is o(Yn).
.
No comments:
Post a Comment