Gaurav's Blog

return rand();

Deathbed Formulae

| Comments

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.

  1. $\large{\left(\frac{y}{x}\right)^{x}} \leq \large{y \choose x} \leq \large{\left(\frac{ey}{x}\right)^{x}}$.

  2. For a large value of $n$, $\left(1 - \large{\frac{1}{n}}\right)^{n} \approx \large{\frac{1}{e}}$.

  3. 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.