Computer Science

Algorithms, information theory and discrete math

This Computer Science formula category brings together key results from algorithms, information theory, and discrete math, from Shannon Entropy and the Master Theorem to binary conversions, Hamming distance, and common time complexities. It’s a practical reference for students, exam prep, and anyone doing real-world programming or systems work, helping you quickly understand data, analyze performance, and solve core computing problems with confidence.

Shannon Entropy

H = -\sum_i p_i \log_2 p_i

Average information content of a random source (bits).

Master Theorem (form)

T(n) = aT(n/b) + f(n)

Analyzes running time of divide-and-conquer algorithms.

Hamming Distance

d(x,y) = \sum_i [x_i \ne y_i]

Number of positions at which two strings differ.

Bits to Represent n

b = \lceil \log_2(n) \rceil

Minimum number of bits to represent n distinct values.

Binary to Decimal

N = \sum_{i=0}^{k} b_i 2^i

Converts a binary number to decimal.

Nodes in a Full Binary Tree

N = 2^{h+1} - 1

Total nodes in a perfect binary tree of height h.

Decimal to Binary

N = \text{repeated division by } 2

Convert a decimal number to binary by dividing by 2 and reading remainders.

Hexadecimal to Decimal

N = \sum_{i=0}^{k} h_i 16^i

Convert a hexadecimal number to decimal.

XOR Operation

a \oplus b = (a \lor b) \land \lnot(a \land b)

Exclusive OR: true when exactly one input is true.

Two's Complement

-N = \lnot N + 1

Represents negative integers in binary by inverting bits and adding one.

Common Time Complexities

O(1) < O(\log n) < O(n) < O(n\log n) < O(n^2) < O(2^n)

Ordering of common algorithmic growth rates.

Logarithmic Time

O(\log n)

Runtime that grows logarithmically with input size.

Linearithmic Time

O(n\log n)

Runtime of efficient comparison sorts.

Quadratic Time

O(n^2)

Runtime that grows with the square of input size.

Exponential Time

O(2^n)

Runtime that doubles with each added element.

Master Theorem Form

T(n) = aT(n/b) + f(n)

General form for analyzing divide-and-conquer recurrences.

Data Transfer Time

t = \frac{S}{R}

Time to transfer data of a given size at a rate.

Address Space

N = 2^n

Number of addressable locations for n bits.

Hexadecimal to Decimal

d = \sum h_i \times 16^i

Convert a hex number to decimal by positional weights.

Parity Bit

p = b_1 \oplus b_2 \oplus \cdots \oplus b_n

XOR of data bits used for error detection.

Nyquist Sampling Rate

f_s \geq 2f_{max}

Minimum sampling rate to capture a signal without aliasing.

Nyquist Data Rate

C = 2B\log_2 L

Maximum data rate of a noiseless channel.

Shannon Channel Capacity

C = B\log_2(1 + SNR)

Maximum error-free data rate of a noisy channel.

Hamming Code Bits

2^r \geq m + r + 1

Parity bits r needed to protect m data bits.

Average Memory Access Time

AMAT = H + M \times P

Effective access time from hit time, miss rate, and penalty.

Amdahl Law

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

Maximum speedup from parallelizing a fraction of a task.

Throughput

X = \frac{N}{T}

Number of operations completed per unit time.