Computer Science Formulas

Computer science has fewer formulas than physics, but the ones it has decide how fast programs run, how small files can get and how many servers a website needs. Each one here comes with numbers you can check by hand.

6 formulas, in the order that makes them easiest to learn:

Binary Number Value

$$N = \sum_{i=0}^{n-1} b_i \cdot 2^{i}$$

Binary uses only the digits 0 and 1, and this formula turns a row of those digits into the ordinary number they stand for.

Binary Search Steps

$$\text{steps} = \lceil \log_2 (n + 1) \rceil$$

Binary search finds an item in a sorted list by checking the middle and throwing away half, and this formula counts how many checks that takes at most.

Shannon Entropy

$$H = -\sum_{i=1}^{n} p_i \log_2 p_i$$

Shannon entropy is one number, in bits, that says how unpredictable a source is. The more predictable it is, the less space its messages need.

Amdahl's Law

$$S = \frac{1}{(1 - p) + \frac{p}{s}}$$

Amdahl’s law tells you how much faster a whole program gets when you speed up only part of its work, and why the part you leave alone caps the gain.

De Morgan's Laws

$$\neg(A \land B) = \neg A \lor \neg B \qquad \neg(A \lor B) = \neg A \land \neg B$$

De Morgan’s laws say that a NOT in front of a group of AND or OR conditions flips the group: AND becomes OR, and OR becomes AND.

Little's Law

$$L = \lambda W$$

Little’s law says the number of things inside a system equals how fast they arrive, multiplied by how long each one stays.

Other subjects: AI & Machine Learning | Electricity | Quantum Mechanics. Plain-text copy: computer-science.md.