# Computer Science Formulas

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

Page: https://formulabro.yunusemrevurgun.com/computer-science/  
Updated: 2026-10-22

## [Binary Number Value](https://formulabro.yunusemrevurgun.com/computer-science/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.

Markdown: https://formulabro.yunusemrevurgun.com/computer-science/binary-number-value.md

## [Binary Search Steps](https://formulabro.yunusemrevurgun.com/computer-science/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.

Markdown: https://formulabro.yunusemrevurgun.com/computer-science/binary-search-steps.md

## [Shannon Entropy](https://formulabro.yunusemrevurgun.com/computer-science/shannon-entropy/)

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

Shannon entropy is one number, measured in bits, that says how unpredictable a source of messages is on average: the more predictable it is, the fewer bits its messages need.

Markdown: https://formulabro.yunusemrevurgun.com/computer-science/shannon-entropy.md

## [Amdahl's Law](https://formulabro.yunusemrevurgun.com/computer-science/amdahls-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.

Markdown: https://formulabro.yunusemrevurgun.com/computer-science/amdahls-law.md

## [De Morgan's Laws](https://formulabro.yunusemrevurgun.com/computer-science/de-morgans-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.

Markdown: https://formulabro.yunusemrevurgun.com/computer-science/de-morgans-laws.md

## [Little's Law](https://formulabro.yunusemrevurgun.com/computer-science/littles-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.

Markdown: https://formulabro.yunusemrevurgun.com/computer-science/littles-law.md

## [Hexadecimal Number Value](https://formulabro.yunusemrevurgun.com/computer-science/hexadecimal-number-value/)

$$
N = \sum_{i=0}^{n-1} d_i \cdot 16^{i}
$$

Hexadecimal counts in sixteens using the digits 0 to 9 and the letters A to F, and this formula turns a hex number into the ordinary number it stands for.

Markdown: https://formulabro.yunusemrevurgun.com/computer-science/hexadecimal-number-value.md

## [Two's Complement](https://formulabro.yunusemrevurgun.com/computer-science/twos-complement/)

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

Two's complement is the usual way computers write negative whole numbers in binary, and this formula reads a bit pattern as a positive or negative number.

Markdown: https://formulabro.yunusemrevurgun.com/computer-science/twos-complement.md

## [Floating-Point Value](https://formulabro.yunusemrevurgun.com/computer-science/floating-point-value/)

$$
x = (-1)^{s} \times 1.f \times 2^{e - 127}
$$

A floating-point number stores a value as a sign, a power of two and a binary fraction, and this formula turns those three parts back into the number.

Markdown: https://formulabro.yunusemrevurgun.com/computer-science/floating-point-value.md

## [Bits Needed](https://formulabro.yunusemrevurgun.com/computer-science/bits-needed/)

$$
b = \lceil \log_2 N \rceil
$$

This formula counts the fewest bits you need so that every one of N items gets its own pattern of 0s and 1s.

Markdown: https://formulabro.yunusemrevurgun.com/computer-science/bits-needed.md

## [Big O Notation](https://formulabro.yunusemrevurgun.com/computer-science/big-o-notation/)

$$
f(n) = O(g(n)) \iff \exists\, c > 0,\ n_0 \text{ such that } 0 \le f(n) \le c\, g(n) \text{ for all } n \ge n_0
$$

Big O notation is a way to say that one function never grows faster than another, once the input is big enough.

Markdown: https://formulabro.yunusemrevurgun.com/computer-science/big-o-notation.md

## [Master Theorem](https://formulabro.yunusemrevurgun.com/computer-science/master-theorem/)

$$
T(n) = a\, T(n/b) + f(n)
$$

The master theorem tells you how long a program takes when it cuts a problem into smaller pieces, solves each piece and joins the answers.

Markdown: https://formulabro.yunusemrevurgun.com/computer-science/master-theorem.md

## [Sum of the First n Integers](https://formulabro.yunusemrevurgun.com/computer-science/sum-of-first-n-integers/)

$$
\sum_{i=1}^{n} i = \frac{n(n+1)}{2}
$$

This formula gives the total of the numbers 1, 2, 3 and so on up to $n$ in one quick calculation, with no adding one number at a time.

Markdown: https://formulabro.yunusemrevurgun.com/computer-science/sum-of-first-n-integers.md

## [Geometric Series](https://formulabro.yunusemrevurgun.com/computer-science/geometric-series/)

$$
\sum_{k=0}^{n-1} r^{k} = \frac{1 - r^{n}}{1 - r} \quad (r \neq 1)
$$

A geometric series adds up a list where each term is the one before it times a fixed number, and this formula finds the whole sum in one step.

Markdown: https://formulabro.yunusemrevurgun.com/computer-science/geometric-series.md

## [Permutations](https://formulabro.yunusemrevurgun.com/computer-science/permutations/)

$$
P(n, k) = \frac{n!}{(n-k)!}
$$

A permutation is one way of picking some items and lining them up in a set order, and this formula counts how many such lineups exist.

Markdown: https://formulabro.yunusemrevurgun.com/computer-science/permutations.md

## [Combinations](https://formulabro.yunusemrevurgun.com/computer-science/combinations/)

$$
C(n,k) = \binom{n}{k} = \frac{n!}{k!\,(n-k)!}
$$

A combination counts the different groups you can pick from a set of items when the order of the picks does not matter.

Markdown: https://formulabro.yunusemrevurgun.com/computer-science/combinations.md

## [Pigeonhole Principle](https://formulabro.yunusemrevurgun.com/computer-science/pigeonhole-principle/)

$$
\max_{j}\, b_j \ge \left\lceil \frac{n}{m} \right\rceil
$$

If you put more things than boxes into the boxes, at least one box must hold two or more things.

Markdown: https://formulabro.yunusemrevurgun.com/computer-science/pigeonhole-principle.md

## [Inclusion-Exclusion Principle](https://formulabro.yunusemrevurgun.com/computer-science/inclusion-exclusion-principle/)

$$
|A \cup B| = |A| + |B| - |A \cap B|
$$

Inclusion-exclusion counts how many items belong to at least one group by adding the groups and then removing the overlaps that were counted twice.

Markdown: https://formulabro.yunusemrevurgun.com/computer-science/inclusion-exclusion-principle.md

## [Hash Table Load Factor](https://formulabro.yunusemrevurgun.com/computer-science/hash-table-load-factor/)

$$
\alpha = \frac{n}{m}
$$

The load factor is how full a hash table is on average: the number of keys divided by the number of buckets.

Markdown: https://formulabro.yunusemrevurgun.com/computer-science/hash-table-load-factor.md

## [Birthday Problem](https://formulabro.yunusemrevurgun.com/computer-science/birthday-problem/)

$$
P(\text{no collision}) = \prod_{k=0}^{n-1}\left(1 - \frac{k}{N}\right) \approx e^{-n(n-1)/(2N)}
$$

The birthday problem asks how likely it is that some pair of items in a random group match, and the answer rises faster than most people expect.

Markdown: https://formulabro.yunusemrevurgun.com/computer-science/birthday-problem.md

## [Bloom Filter False Positive Rate](https://formulabro.yunusemrevurgun.com/computer-science/bloom-filter-false-positive-rate/)

$$
p \approx \left(1 - e^{-kn/m}\right)^{k}
$$

This formula gives the chance that a Bloom filter, a small memory-saving checklist, wrongly says an item is on the list, based on how many bits and checks it uses.

Markdown: https://formulabro.yunusemrevurgun.com/computer-science/bloom-filter-false-positive-rate.md

## [Modulo Operation](https://formulabro.yunusemrevurgun.com/computer-science/modulo-operation/)

$$
a \bmod n = a - n \left\lfloor \frac{a}{n} \right\rfloor
$$

The modulo operation gives the leftover amount after you split one whole number into as many equal full groups of another number as you can.

Markdown: https://formulabro.yunusemrevurgun.com/computer-science/modulo-operation.md

## [Euclidean Algorithm](https://formulabro.yunusemrevurgun.com/computer-science/euclidean-algorithm-gcd/)

$$
\gcd(a, b) = \gcd(b,\ a \bmod b), \qquad \gcd(a, 0) = a
$$

The Euclidean algorithm finds the largest number that divides two numbers evenly, by replacing the pair with a smaller pair again and again until the remainder is zero.

Markdown: https://formulabro.yunusemrevurgun.com/computer-science/euclidean-algorithm-gcd.md

## [RSA Encryption](https://formulabro.yunusemrevurgun.com/computer-science/rsa-encryption/)

$$
c = m^{e} \bmod n, \qquad m = c^{d} \bmod n
$$

RSA lets anyone lock a message with a public key while only the owner can unlock it with a private key, because undoing a product of two secret primes is very hard.

Markdown: https://formulabro.yunusemrevurgun.com/computer-science/rsa-encryption.md

## [Hamming Distance](https://formulabro.yunusemrevurgun.com/computer-science/hamming-distance/)

$$
d(x, y) = \sum_{i=1}^{n} [x_i \ne y_i]
$$

Hamming distance counts the spots where two same-length codes differ, such as the bits in two binary words, and that count shows how many errors a code can catch.

Markdown: https://formulabro.yunusemrevurgun.com/computer-science/hamming-distance.md

## [Password Entropy](https://formulabro.yunusemrevurgun.com/computer-science/password-entropy/)

$$
H = L \log_2 N
$$

Password entropy is a score in bits that counts how many passwords a random generator could have made, so a higher score means guessing one is harder.

Markdown: https://formulabro.yunusemrevurgun.com/computer-science/password-entropy.md

## [Data Transfer Time](https://formulabro.yunusemrevurgun.com/computer-science/data-transfer-time/)

$$
t = \frac{S}{B}
$$

Data transfer time tells you how long a file takes to send: divide its size by the link's speed, using units that match.

Markdown: https://formulabro.yunusemrevurgun.com/computer-science/data-transfer-time.md

## [Bandwidth-Delay Product](https://formulabro.yunusemrevurgun.com/computer-science/bandwidth-delay-product/)

$$
\text{BDP} = B \times \text{RTT}
$$

The bandwidth-delay product tells you how much data must be in transit at once to keep a network link full.

Markdown: https://formulabro.yunusemrevurgun.com/computer-science/bandwidth-delay-product.md

## [Nyquist Sampling Theorem](https://formulabro.yunusemrevurgun.com/computer-science/nyquist-sampling-theorem/)

$$
f_s > 2 f_{\max}
$$

The Nyquist sampling theorem says you must measure a signal more than twice for each cycle of its fastest wave, or the recording comes out distorted.

Markdown: https://formulabro.yunusemrevurgun.com/computer-science/nyquist-sampling-theorem.md

## [Shannon-Hartley Theorem](https://formulabro.yunusemrevurgun.com/computer-science/shannon-hartley-theorem/)

$$
C = B \log_2\left(1 + \frac{S}{N}\right)
$$

The Shannon-Hartley theorem gives the fastest error-free rate, in bits per second, that a noisy channel can carry, based on its width and how strong the signal is compared with the noise.

Markdown: https://formulabro.yunusemrevurgun.com/computer-science/shannon-hartley-theorem.md

## [Average Memory Access Time](https://formulabro.yunusemrevurgun.com/computer-science/average-memory-access-time/)

$$
\text{AMAT} = t_{\text{hit}} + r_{\text{miss}} \times t_{\text{penalty}}
$$

AMAT is the average time it takes a computer to fetch one piece of data, when most fetches are quick and a few are slow.

Markdown: https://formulabro.yunusemrevurgun.com/computer-science/average-memory-access-time.md

## [CPU Time Equation](https://formulabro.yunusemrevurgun.com/computer-science/cpu-time-equation/)

$$
T_{\text{CPU}} = IC \times CPI \times t_{\text{clock}} = \frac{IC \times CPI}{f}
$$

The CPU time equation says how many seconds a processor spends on a program, using three counts: the steps the program takes, the clock ticks each step needs, and how fast the clock ticks.

Markdown: https://formulabro.yunusemrevurgun.com/computer-science/cpu-time-equation.md

## [Gustafson's Law](https://formulabro.yunusemrevurgun.com/computer-science/gustafsons-law/)

$$
S = N - s\,(N - 1)
$$

Gustafson's law estimates how much more work a computer with many workers can finish in the same time, when the job grows as you add workers.

Markdown: https://formulabro.yunusemrevurgun.com/computer-science/gustafsons-law.md

## [System Availability](https://formulabro.yunusemrevurgun.com/computer-science/system-availability/)

$$
A = \frac{\text{MTBF}}{\text{MTBF} + \text{MTTR}}
$$

System availability is the share of time a system is up and working, based on how often it breaks and how long each repair takes.

Markdown: https://formulabro.yunusemrevurgun.com/computer-science/system-availability.md

## [M/M/1 Queue](https://formulabro.yunusemrevurgun.com/computer-science/mm1-queue/)

$$
W = \frac{1}{\mu - \lambda}
$$

The M/M/1 formula tells you the average time an item spends in a line with one server, based on how fast items arrive and how fast the server works.

Markdown: https://formulabro.yunusemrevurgun.com/computer-science/mm1-queue.md

## [Perfect Binary Tree Nodes](https://formulabro.yunusemrevurgun.com/computer-science/perfect-binary-tree-nodes/)

$$
N = 2^{h+1} - 1
$$

The formula counts every node in a perfect binary tree, a branching diagram in which each row is completely full, using only the number of rows below the top.

Markdown: https://formulabro.yunusemrevurgun.com/computer-science/perfect-binary-tree-nodes.md

## [Complete Graph Edges](https://formulabro.yunusemrevurgun.com/computer-science/complete-graph-edges/)

$$
E = \frac{n(n-1)}{2}
$$

A complete graph joins every pair of points with one line, and this formula counts how many lines that takes, given how many points there are.

Markdown: https://formulabro.yunusemrevurgun.com/computer-science/complete-graph-edges.md

## [Euler's Formula for Planar Graphs](https://formulabro.yunusemrevurgun.com/computer-science/eulers-formula-for-planar-graphs/)

$$
V - E + F = 2
$$

Euler's formula says that if you draw a connected network on a flat sheet with no crossing lines, then corners minus lines plus regions always comes to 2.

Markdown: https://formulabro.yunusemrevurgun.com/computer-science/eulers-formula-for-planar-graphs.md

## [PageRank](https://formulabro.yunusemrevurgun.com/computer-science/pagerank/)

$$
PR(p) = \frac{1 - d}{N} + d \sum_{q \to p} \frac{PR(q)}{L(q)}
$$

PageRank gives each web page a score based on which other pages link to it, and a link from a page with a high score counts for more.

Markdown: https://formulabro.yunusemrevurgun.com/computer-science/pagerank.md

## [TF-IDF](https://formulabro.yunusemrevurgun.com/computer-science/tf-idf/)

$$
\text{tfidf}(t, d) = \text{tf}(t, d) \times \ln\frac{N}{\text{df}(t)}
$$

TF-IDF gives a word a high score in a document when the word appears often there but rarely across all the other documents.

Markdown: https://formulabro.yunusemrevurgun.com/computer-science/tf-idf.md