Skip to content

Instantly share code, notes, and snippets.

@loyd
Last active June 14, 2023 08:47
Show Gist options
  • Save loyd/8356f1de41008408c23e2c1b4aac4e40 to your computer and use it in GitHub Desktop.
Save loyd/8356f1de41008408c23e2c1b4aac4e40 to your computer and use it in GitHub Desktop.
Useful approximations

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.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment