Asymptotic Analysis

See existing notes here

Analysis happens primarily for computer algorithms but you you need to know if a function is big O of another function in an abstract sense. Basically, is the function always bounded above by the other function regardless of input.

Proving a function bounds another involves setting up an inequality and transforming it so that it is obvious.

todo: what is a "witness" in a proof like this? idk

O is bounds above Ω is bounds below Θ is grows at the same rate