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.
Then we talk about some basic mathematics functions such as polynomial and 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.
There isn’t a clear formula for factorial, but the Stirling’s approximation is a good approximate for factorial.
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.