Concepts2

Double Counting

Double counting is the strategy of counting the same quantity in two different ways to derive an equality or an efficient algorithm.

#double counting#contribution technique#handshake lemma+12

∑MathIntermediate

Harmonic Lemma

The Harmonic Lemma says that the values of \lfloor n/i \rfloor only change about 2\sqrt{n} times, so you can iterate those value blocks in O(\sqrt{n}) instead of O(n).

#harmonic lemma#integer division trick#block decomposition+12