Calculus×Computing
ES

Integral test

Level UniversityDifficulty ★★★★★Concept⌖ Open in the map

What is it?

For positive decreasing ff, ∑f(k)\sum f(k) and ∫1∞f\int_1^\infty f converge or diverge together, and the integral estimates the sum: that is how Hn≈ln⁡nH_n \approx \ln n is obtained.

Formulas

∫1n+1f(x) dx≤∑k=1nf(k)≤f(1)+∫1nf(x) dx\int_1^{n+1} f(x)\,\dd x \le \sum_{k=1}^{n} f(k) \le f(1) + \int_1^{n} f(x)\,\dd x

Where it shows up in computing

  • Algorithm analysis and complexity★★★★★frequentScientific computing and algorithms

    Turning sums like ∑k≤nlog⁡k\sum_{k\le n} \log k into integrals gives log⁡n!=nlog⁡n−n+O(log⁡n)\log n! = n\log n - n + O(\log n).

Where is it used?

Computing topics reachable from here, through the chain of ideas that leads to them:

λ Scientific computing and algorithms

This page has the essentials. A fuller treatment (intuition, formal definition, worked example) is on the way.

↑ ↓ to navigate · ↵ · Esc