Asymptotics From Scratch

Table of Contents

Exp & Log Functions

Explained here (Clemson Math 1060 sec 1.3). These Clemson U lectures average ~20m and are just the right difficulty if you forgot high school like most people so gaps will be filled in and there's lot's of constructions instead of descriptive/abstract definitions.

Logarithmic inverses, why does \(\large b^{log_b{(x)}} = x\)?

  • \(\large 2^{log_2{(1)}} = 2^0 = 1\)
  • \(\large 2^{log_2{(2})} = 2^1 = 2\)
  • \(\large 2^{log_2{(3})} \approx 2^{1.6} \approx 3\)
  • \(\large 2^{log_2{(4})} = 2^2 = 4\)

A base e log or ln(x) is often used in computer science literature instead of base 2 because \(\large log_{2}(x) = \frac{ln(x)}{ln(2)}\) meaning you are off only by a constant factor and now can enjoy all the nice properties ex and ln(x) have for doing quick approximations by hand. For small inputs where x2 is evaluated smaller than x then ex can be approximated with 1 + x and ln(1 - x) can be approximated with -x. To see how etime = growth and ln(growth) = time then read this.

Notice how a log is a linearization of an exponent, if you log 2x then log(2x) = xlog(2) and you mapped a quadratic to a linear space.

Trig Functions

Examples are frequently done using trig functions in all literature for analysis/calculus so you may as well get this over with.

If you don't remember trig at all try this (Math 1060 sec 1.4) review of Trig functions and their inverses. Skip through and remind yourself that sin-1 is not 1/sin. Where do those square root x/y coords come from on the unit circle? Explained in the Trig Boot Camp (Brown University). Two right angle triangles (deg 30/60/90 and 45/45/90) need to be scaled down so the hypotenuse is 1 to fit on the unit circle.

We have just seen another linearization. Watch a few minutes of this (Wildberger Rational Trig) starting @5:56 to see motion around a nonlinear curve being mapped to the linear motion of the two axis moving back and forth.

Limits

Skim through these, if you want to do exercises pause the video before he works out an example and do it yourself. Limits will come up all the time.

We need limits where f(x) inputs go to infinity

  • Limits at Infinity (Math 1060 2.5) a polynomial is a way to model a function and get all it's properties like what is the behavior at f(0) or f(x) = 0. Algorithm cost functions are going to be a polynomial or a recurrence relation with a characteristic polynomial too.
  • Continuity crash course on continuity on an interval.

We need LimSup and LimInf

The notation here for convergence, if an represents the sequence 1/n then it is convergent if abs(limit - an) < every positive epsilon meaning as inputs continue they always get closer to the limit which here is zero. Epsilons are small displacements/decimals like 0.0001 but notice here it says every epsilon because with infinity the process of inputting a bigger denominator to 1/n doesn't stop.

Imagine a function with inputs growing forever and every output is appended to a list. You can filter the list to take out whatever subsequence you wanted like all the even/odd elements or any elements within a small epsilon displacement of each other meaning they are clustered together. LimSup goes to negative infinity if there is no supremum limit because it searches right to left or positive to negative. LimInf is positive infinity if no infimum limit found as it searches left to right from negative to positive.

Derivatives

  • Derivative (Math 1060 3.1) shows the geometry of a derivative at a point.
  • Derivative as a Function or x -> x2 derivative returns x -> 2x for all 'points'/inputs
  • Derivative Rules the usual formulas, higher-order derivatives, ex is it's own derivative, and remark that differentiation is a linear operator.
  • L'Hopitals Rule I and II is presented as the definition of big-O in some texts.

Derivative rules to watch when needed.

Once you learn asymptotics you can come back and apply it when finishing calculus.

  • Product Rule (Math 1060 3.4) (fg)' = f'g + fg' and (f/g)' = (f'g - fg')/g2
  • Trig Derivatives covers reciprocal limits too. Lightly skim this just so you know the derivative of sinx is cosx and that if you take the derivative of sinx 4x then it's a cycle that returns to sinx.
  • Rates of Change explains real life calculus meaning economic cost function derivatives and physics how the derivative of f(time) = position gives you f(time) = velocity. You can undo the velocity derivative to go back to the position function using indefinite integration.
  • Chain Rule the derivative of function composition or f'(g)*g'
  • Derivatives of Log/Exp the derivative of ex or exp(x) is itself.

Optimization to watch when needed.

Integrals

This is what we really need.

Watch when needed.

That's it!

Asymptotics

Buy, borrow or download Asymptopia by Joel Spencer.

Big-O (and Friends) TODO

Resources

  • Clemson University Math 1060 course page and list of lectures they use the book Calculus: Early Transcendentals Briggs Et. al
  • Julian Grossmann personal site and YouTube playlist of Real Analysis. Look at his setup you don't need expensive tools to make a YouTube video.
  • Real Analysis books: (free) here the elementary and graduate book contains hints to all proofs and was written by active researchers so they tell you why the theorems matter and which don't matter like Rolle's Theorem or the Riemann integral. Andy Bruckner is 91 years old and still publishing papers.