# 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 means is tightly bounded by n within a constant factors. There exist positive constants such that to the right of , the value of will always lies between .

Big-O gives us an upper bound in the same fashion. Big-Omega gives us the asymptotic lower bound. means passing certain , the value of is always above for some constant

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 it means the bound holds for all constants c > 0. Intuitively, for large enough n, becomes insignificant.

# Math magic

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

## Exponential

so So the exponential with a base strictly bigger than 1, will grow faster than any polynomial function.

Then we Taylor Expand 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

We have proven a formula for related to the golden ration

Where is the conjugate of the golden ration.

We can manipulate a bit to find that . Which means the ith Fib is equal to rounded to the nearest integer.