Useful approximations

approximations.md

Useful approximations

Just random approximations sometimes useful in work for "mental" calculation.

Bloom filter, space

b(p) ≈ 1.44 * log₂(p)

• b — bits per element
• p — false positive probability

p	b
5.0%	6
2.0%	8
1.0%	10
0.5%	11
0.1%	14

More info.

Birthday problem

p(n, d) ≈ 1 - exp(-n² / 2d)

• p — colision probability
• n — number of elements
• d — "days", space size

More info.

Little's law

Only for stable systems!

L = λ * W

• L — long-term average number
• λ — average arrival rate
• W — average processing time

More info.