Standard Notation and Common Functions

Transitivity:

f (n) = A ( g (n) ) and g (n) = A ( h (n) )  Þ f (n) = A ( h (n) )

Reflexivity:

f (n) = A ( f (n) ) ,  A Î { Q, O, W }

Symmetry:

f (n) = Q ( g (n) ) Û  g (n) = Q ( f (n) )

Transpose Symmetry:

f (n) = O ( g (n) ) Û g (n) =  W ( f (n) )

Heuristics:

Trichotomy of real Numbers:

If a and b are real then one of three is true:

1. a > b
2. a < b
3. a = b

There is no analogy for functions

Increasing and Decreasing Functions:

The function 'f' is monotonically increasing if m £ n Þ f (m) £ f (n)

The function 'f' is monotonically decreasing if m £ n Þ f (m) ³ f (n)

The function 'f' is strictly increasing / decreasing  if m < n Þ f (m) > / < f (n)

Floor and Ceiling:

" real x :: x - 1 < ë x û £ x  £ é x ù < x + 1

so floor rounds to the left, and ceiling rounds to the right

" integers n :: n = é n/2 ù  + ë n/2 û

" integers n, and integers a ¹ 0 ¹ b :: é é n/a ù /b ù = é n/ab ù and ë ë n/a û /b û = ë n/ab û

Polynomials:

 

p (n)   =

d å j = 1

ai ni   ,       ad ¹ 0

{ ao, ... ,ad } coefficients

p (n) is asymptotically positive if a _d > 0.  If " a ³ 0 , n^a  then is monotonically increasing.

f (n) is polynomially bounded if f (n) = n ^{O (1)} or f (n) =  O (n ^k) for some constant k

Exponentials:

" a ¹ 0, m, n real :: a⁰ = 1,  a¹ = a, a ^-1 = 1 / a

(a^m) ⁿ = a ^mn , (a^m) ⁿ  = (a ⁿ )^m , a^ma ⁿ = a^m+n

lim n ® ¥

ab / an = 0

, a > 1, b a constant

Bounds:

 

ex = 1 + x + x2 / 2! + ... =

¥ å j = 0

xi / i!

e^x ³ 1 + x, " x

1 + x £ e^x £ 1 + x + x² , |x| £ 1

so  e^x  =  1 + x + Q ( x² ), and

lim n ® ¥

( 1 + x / n )n

= ex  (compound interest)

Logarithms:  (inverses of exponentials)

lg n = log₂ n,  ln n = log_e n

lg^k n = (lg n )^k , lg lg n = lg ( lg n )

a = b ^{log_b a}, log_c (ab) = log_c a + log_c b

 log_b aⁿ = n  log_ba , log_b a = log_c a / log_c b

 log_b1/a =  - log_ba

 log_b a =  1 / log_ab , a^{log_b n} = n^{log_b a}

 

When |x| < 1 ln ( 1 + x ) = { x - x²/2 + x³/3 - ...}

For x > -1 , x / ( x + 1 ) £ ln ( 1 + x ) £ x

f (n) is poly-logarithmically bounded if f (n) = lg^{O (1)} n .

lim n ® ¥

lgb n /  2a lg n =

lim n ® ¥

= lgb n /  na = 0

Therefore lg^b n = o ( n^a )

Note: logs < polynomials < exponentials !

Factorials:

n! = 1 if n = 0, and n( n -1 )! if n > 0, so n! = ( 1 * 2 * 3 * ...n)}.

Clearly n! £ nⁿ , however a better bound is Sterling's approximation:

n!   =   Ö( 2 p n ) * ( n / e )ⁿ * ( 1 + Q ( 1 / n ) )

n! = o ( nⁿ ) , and w ( 2ⁿ )

Ö( 2 p n ) * ( n / e )ⁿ  £ n! £ Ö( 2 p n ) * ( n / e )^{n +1/12n}

 G ( z ) = ₀ò^¥t^{z - 1} e^-t dt , G ( n + 1 ) = n!

The Gamma function gives Stirling's approximation.

G ( z ) = Ö( 2 p ) e^z  z^z-1/2 [ 1 + 1/12z + 1/288z² - 139/51840z³ ] fleshed out S. A.  Þ Q (1/2) ]

Iterated logarithm or "log star" function:

Define: lg ⁽ⁱ⁾ (n) = n if i = 0
           lg ( lg ^(n-i)) if  i > 0 & lg ^{(i - 1)} > 0
           undefined  otherwise
Note: lg ⁱ (n)  ¹  (lg n ) ⁱ

lg ^* n = min { i ³ 0 : lg ⁽ⁱ⁾ £ 1 }

n	2	4	16	216	2(216)
lg * n	1	2	3	4	5

 

                               2
                              .
                             . 
                            .
                           .
                          2
      tower = lg * n     2
      

 The log * n function counts the size of the tower of exponentials above the 2.

Note that the lg * n is the inverse of the Ackerman function

Fibonacci Numbers

F₀ = 0, F₁ = 1, F_{n + 2} = F_{n + 1}+ F_n    where n = 0,1,2,3...
F_n = The number of rabbits at a generation
New rabbits = old rabbits + born rabbits

What if F_n = c lⁿ

 c lⁿ⁺²  = c lⁿ⁺¹  + c lⁿ  if you you divide by  c lⁿ  Þ  l² = l + 1,  l  must solve

f ( ) = l²- l - 1 = 0, 

called the characteristic polynomial of the Fibonacci recursion F_{n + 2} = F_{n + 1}+ F_n

l    =   (1 +/- Ö (1 + 4 )) / 2 = (1 +/- Ö5 ) / 2
f   =   (1 + Ö5)/ 2 = 1.61803...   called the golden ratio
f^{^}   =   (1 - Ö5)/ 2 = -.61803...

F_n = c₁fⁿ + c₂f^{^n}
F₀ = c₁ + c₂ =  0
F₁ =  c₁f + c₂f^{^} = c ( f - f^{^} ) = 1
 f - f^{^} = (1/2 + Ö5/2 ) - (1/2 - Ö5/2 ) = Ö5
c = 1/Ö5 Þ  F_n= ( fⁿ - f^{^n}) / Ö5  
since | f^{^} | <   we have:   F_n = round ( fⁿ / Ö5 )