Professor Bender asked us to remember three ‘Deathbed Formulae’, i.e., if someone asks you about them on your deathbed, you should be able to recall these.
-
$\large{\left(\frac{y}{x}\right)^{x}} \leq \large{y \choose x} \leq \large{\left(\frac{ey}{x}\right)^{x}}$.
-
For a large value of $n$, $\left(1 - \large{\frac{1}{n}}\right)^{n} \approx \large{\frac{1}{e}}$.
-
For a large value of $n$, $\left(1 + \large{\frac{1}{n}}\right)^{n} \approx e$.
These were super-helpful in the Graduate-level Algorithms and Advanced Algorithms courses, which were heavy on randomized algorithms.
I might post about some interesting bits related to randomized algorithms some time soon, so wanted to share these pre-emptively.