Chapter 3 Growth of function

Asymptotic notation

This chapter talks about the rigorous mathematics formula behind the Big-O, Big-Omega and other notation. Since this chapter is skipped in the MIT open course, I will be brief.

Basically f(n) \in \Theta(g(n)) means f(n) is tightly bounded by n within a constant factors. There exist positive constants n_0, c_1, c_2 such that to the right of n_0, the value of f(n) will always lies between c_1g(n), c_2 g(n).

Big-O gives us an upper bound in the same fashion. Big-Omega \Omega gives us the asymptotic lower bound. f(n) \in \Omega(g(n)) means passing certain n_0, the value of f(n) is always above c_1g(n) for some constant c_1.

When we have a asymptotic notation in the function, we will interpret it as some anonymous function that we don’t care to name.

We also have little-o and little-omega to non-asymptotically tight bounds. If we have f(n) = o(g(n)) it means the bound 0 \leq f(n) < cg(n) holds for all constants c > 0. Intuitively, for large enough n, f(n) becomes insignificant.

Math magic

Then we talk about some basic mathematics functions such as polynomial and exponential.

Exponential

\lim_{n \rightarrow \infty} \dfrac{n^b}{a^n} = 0 so n^b = o(a^n) So the exponential with a base strictly bigger than 1, will grow faster than any polynomial function.

Then we Taylor Expand e^x to talk about some property.

Factorial

There isn’t a clear formula for factorial, but the Stirling’s approximation is a good approximate for factorial.

Fibonacci number

F_0 = 0, F_1 = 1, F_i = F_{i - 1 } + F_{i - 2}

We have proven a formula for F_i related to the golden ration \phi

F_i = \dfrac{\phi ^ i - \hat{\phi^i}}{\sqrt{5}}

Where \hat{\phi ^i} is the conjugate of the golden ration.

We can manipulate a bit to find that F_i = \floor{ \dfrac{\phi^i}{\sqrt{5}} + \dfrac{1}{2}}. Which means the ith Fib is equal to \dfrac{\phi^i}{\sqrt{5}} rounded to the nearest integer.

Leave a Reply

Your email address will not be published. Required fields are marked *

To create code blocks or other preformatted text, indent by four spaces:

    This will be displayed in a monospaced font. The first four 
    spaces will be stripped off, but all other whitespace
    will be preserved.
    
    Markdown is turned off in code blocks:
     [This is not a link](http://example.com)

To create not a block, but an inline code span, use backticks:

Here is some inline `code`.

For more help see http://daringfireball.net/projects/markdown/syntax