*Notes to a video lecture on http://www.unizor.com*

__Rate of Change: Big-O, Little-o__

Consider two infinitely growing sequences

{

**} and {**

*n***}.**

*n+1*Both are infinitely growing, the second one is always (for any order number

**) greater than the first, so it is "bigger" in some sense.**

*n*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

**, but their values are getting larger and larger, so proportional difference is getting more and more negligible. For order number**

*1***the difference of**

*n=10***represents 10% of the value, for**

*1***the difference of**

*n=1000***represents only 0.1% of the value. This allows us to say that both sequence are growing at the same**

*1**rate*.

On the other hand, if you consider these infinitely growing sequences

{

**} and {**

*n***},**

*ln(n)*you will soon see that proportional difference becomes larger and larger as

**growth much faster than**

*n***. For order number**

*ln(n)***the first sequence has value**

*n=10***, while the second, approximately, has**

*10***- 77% difference. For**

*2.3***the first sequence has value**

*n=1000***, while the second, approximately, has**

*1000***- 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**

*6.9**rate*of growth of the first sequence is greater than of the second.

Similar situation is with infinitesimals.

Consider two infinitesimal sequences

{

**} and {**

*1/n***}.**

*10/n*Both are infinitesimal, though the first one is always smaller. Proportional difference between them is always

**, 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.**

*9/n*On the other hand, if you consider these infinitesimals

{

**} and {**

*1/n***},**

*1/ln(n)*you will see that proportional difference is increasing as

**converges to zero much faster than**

*1/n***. Indeed, with order number**

*1/ln(n)***the first sequence equals**

*n=10***, while the second, approximately, is**

*0.1***- more than 300% difference. For**

*0.4343***the first sequence is**

*n=100***, while the second, approximately, is**

*0.01***- more than 2000% difference. For**

*0.2174***the first sequence is**

*n=1000***, while the second is**

*0.001***- more than 14000% difference.**

*0.1448*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

**- to indicate the same rate of change or the same order of growing,**

*n+1 = O(n)***- to indicate that**

*ln(n) = o(n)***is "smaller" in a sense of the rate of growing of**

*ln(n)***to infinity is slower than the rate of growing of**

*ln(n)***.**

*n*For infinitesimal sequences we can say that

**- to indicate that both infinitesimals are diminishing to zero with the same speed, their order of diminishing is the same,**

*10/n = O(1/n)***- to indicate that**

*1/n = o(1/ln(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/n***.**

*1/ln(n)*Let's now define

**Big-O**and

**Little-o**more rigorously.

Consider two sequences

{

**} and {**

*X*_{n}**}.**

*Y*_{n}Definition of

**Little-o**is based on the behavior of their ratio {

**} (assuming**

*X*_{n}/Y_{n}**).**

*Y*_{n}≠0If this ratio is an infinitesimal sequence, we say that

**)**

*X*_{n}= o(Y_{n}Symbolically, the rate of change of

**is**

*X*_{n}**) if**

*o(Y*_{n}∀

**∃**

*ε>0***:**

*N***⇒**

*n ≥ N***|**≤

*X*|_{n}/Y_{n}

*ε*Definition of

**Big-O**for two positive infinitely growing or infinitesimal sequences {

**} and {**

*X*_{n}**} is also based on the ratio {**

*Y*_{n}**}.**

*X*_{n}/Y_{n}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

**is**

*X*_{n}**) if**

*O(Y*_{n}∃

**,**

*A > 0***,**

*B > 0***:**

*N***⇒**

*n ≥ N*

*A ≤ X*_{n}/Y_{n}≤ B*Examples*

*1. Infinitely Growing -*

**O()****;**

*X*_{n}= 2n²+n−1

*Y*_{n}= n²−1**=**

*X*_{n}/Y_{n}= (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

**and**

*A=2***for**

*B=3***.**

*n ≥ 2*Therefore,

**is**

*X*_{n}**).**

*O(Y*_{n}*2. Infinitesimals -*

**O()****;**

*X*_{n}= 1/n

*Y*_{n}= n/(n²−1)**=**

*X*_{n}/Y_{n}= (n²−1)/n²=

*1−1/n²*The last expression is, obviously, limited between

**and**

*A=0.5***for**

*B=1***.**

*n ≥ 2*Therefore,

**is**

*X*_{n}**).**

*O(Y*_{n}*3. Infinitely growing -*

**o()****;**

*X*_{n}= ln(n)

*Y*_{n}= n**=**

*X*_{n}/Y_{n}= ln(n)/n

*ln(n*^{1/n})Expression

**converges to**

*n*^{1/n}**.**

*1*Here is a proof (with a help of a trick).

Let

**.**

*Z*_{n}=n^{1/n}−1Obviously,

**.**

*Z*_{n}≥ 0Consider an expression

**.**

*(1+Z*_{n})^{n}On one hand, it is equal to

**.**

*(1+n*^{1/n}−1)^{n}= nOn the other hand, let's use Newton's binomial for it:

**= Σ**

*(1+Z*_{n})^{n}_{i∈[0,n]}

*C*_{n}^{i}Z_{n}^{i}Replacing the left side with

**and leaving only one member of the sum on the right - the one with**

*n***- we come up with the following inequality:**

*Z*_{n}^{2}

*n ≥ C*_{n}^{2}Z_{n}^{2}Since

**,**

*C*_{n}^{2}= n(n−1)/2**or**

*n ≥ Z*_{n}^{2}n(n−1)/2**,**

*Z*_{n}^{2}≤ 2/(n−1)which proves that

**is an infinitesimal variable and, therefore,**

*Z*_{n}**.**

*n*^{1/n}→1Therefore,

**is converging to**

*ln(n*^{1/n})**.**

*0*Therefore,

**is**

*X*_{n}**).**

*o(Y*_{n}*4. Infinitesimals -*

**o()****;**

*X*_{n}= 1/2^{n}

*Y*_{n}= 1/n

*X*_{n}/Y_{n}= n/2^{n};The expression

**is converging to zero.**

*n/2*^{n}Here is a proof.

Use Newton's binomial for identity

*2*^{n}= (1+1)^{n}**= Σ**

*2*^{n}_{i∈[0,n]}

*C*_{n}^{i}Using only one member of the sum on the right, we come up with an inequality

**≥**

*2*^{n}

*n(n−1)/2*from which follows

**.**

*n/2*^{n}≤ 2/(n−1)Therefore,

**is an infinitesimal.**

*n/2*^{n}Therefore,

**is**

*X*_{n}**).**

*o(Y*_{n}.