List of calculation rules for asymptotic notation?

1.6k Views Asked by At

Background: I am working my way through CLR/CLRS's proof of the master theorem (section 4.4 in the 1st and 2nd editions of Introduction to Algorithms), and I'm doing my own write-up of this proof1 where I make clear what theorems are used, specifically the theorems about asymptotic notation.

As one example, I discovered that this proof when proving (4.13) (this part has been dropped in the 2nd edition) silently uses the fact that $\;f(x) = O(1) \text{ for } x \to \infty\;$ implies $\;g(f(x)) = \Theta(1) \text{ for } x \to \infty\;$, if $\;f \in \mathbb R \to \mathbb N\;$ and $\;g \in \mathbb N \to \mathbb R\;$.

There are of course many more such rules, like $\;f(x) = O(g(x))\;$ implies $\;f(x) + g(x) = O(g(x))\;$, etc.

My question: Where can I find an overview list of such 'calculation rules' for asymptotic notation?

1In Dijkstra-Scholten and Gries-Schneider's calculational proof style, in response to a 17 year old challenge by Brian Borchers.