調和級数が log(n) で押さえられることの証明
競技プログラミングで計算量を計算するときにたまに出てくるのが調和級数のオーダーが$ O(\log n)、つまり $ 1 + \dfrac{1}{2} + \dfrac{1}{3} + \cdots + \dfrac{1}{n} \sim O(\log n)という式。たとえば AGC 027 B Garbage Collector でも使った。 ぱっと見ると自明ではないが、積分を使うと、簡単に証明できる（高校のときに調和級数が発散する証明でやったのと同じ手法。ただし上から押さえるのが違う）。
上図のように$ S_n = 1 + \dfrac{1}{2} + \dfrac{1}{3} + \cdots + \dfrac{1}{n} \lt \int_0^n \dfrac{1}{x} dxと押さえられるので、$ \int_0^n \dfrac{1}{x} dx = \log n - 1から$ S_n \sim O(\log n)となる。なお、$ -1はオーダーなので無視できる。
なお同様にして下から押さえることもできる。