Algebra#

Algebra is the machinery for manipulating symbols and solving equations — the language in which algorithms express their relationships, complexity bounds are derived, and configuration parameters are computed.

Expressions, Equations, and Identities#

Expressions#

An expression is a mathematical phrase that combines numbers, variables, and operations. It does not have an equals sign.

3x + 7
n² - 1
log₂(n) + 1

Equations#

An equation asserts that two expressions are equal. It can be solved for unknowns.

3x + 7 = 22    →  x = 5
n² - 1 = 0     →  n = ±1

Identities#

An identity is an equation that holds for all values of the variables.

(a + b)² = a² + 2ab + b²           (always true)
a² - b² = (a + b)(a - b)           (always true)

Manipulating Equations#

Every equation manipulation must preserve equality — whatever you do to one side, do to the other.

Warning: Squaring both sides can introduce extraneous solutions. Always verify results.

Systems of Equations#

When you have multiple unknowns, you need as many independent equations as unknowns.

Substitution method:

Given:  x + y = 10
        2x - y = 5

From equation 1:  y = 10 - x
Substitute into 2: 2x - (10 - x) = 5
                    3x - 10 = 5
                    3x = 15
                    x = 5, y = 5

Engineering application: Solving for unknowns in capacity planning — if you know total requests and the ratio between read and write operations, you can solve for each.

Exponents and Roots#

Exponent Rules#

Why Exponents Matter in Computing#

Exponential growth appears everywhere:

The “rule of 72”: an investment growing at r% per period doubles in approximately 72/r periods. A service with 10% weekly traffic growth doubles in ~7 weeks.

Logarithms#

A logarithm answers: “to what power must I raise the base to get this number?”

log_b(x) = y  means  b^y = x

Common Bases#

Logarithm Rules#

Logarithms in Computer Science#

Key Intuition#

Logarithms convert multiplication into addition and exponentiation into multiplication. This is why they appear naturally whenever:

• A problem is solved by repeated halving (binary search, divide-and-conquer)
• You need to count how many digits a number has (⌊log₁₀(n)⌋ + 1)
• You measure orders of magnitude (decibels, Richter scale, pH)

Polynomials#

A polynomial is an expression of the form:

p(x) = aₙxⁿ + aₙ₋₁xⁿ⁻¹ + ... + a₁x + a₀

The degree is the highest power of x with a nonzero coefficient.

Common Polynomial Forms#

The Quadratic Formula#

For ax² + bx + c = 0:

x = (-b ± √(b² - 4ac)) / (2a)

The discriminant (b² - 4ac) determines the nature of solutions:

Factoring Common Patterns#

a² - b²           = (a + b)(a - b)          Difference of squares
a² + 2ab + b²     = (a + b)²                Perfect square
a³ - b³           = (a - b)(a² + ab + b²)   Difference of cubes
x² + (a+b)x + ab  = (x + a)(x + b)          Factoring trinomials

Engineering application: Polynomial evaluation is at the heart of hash functions, CRC calculations, and interpolation. Horner’s method evaluates a degree-n polynomial in O(n) operations:

p(x) = ((aₙx + aₙ₋₁)x + aₙ₋₂)x + ... + a₀

Summation and Product Notation#

Compact notation for expressing sums and products over a range.

Sigma Notation (Summation)#

 n
 Σ  f(i)  =  f(1) + f(2) + ... + f(n)
i=1

Common Sums#

Why These Sums Matter#

• Σ i = n(n+1)/2 explains why nested loops give O(n²) complexity: iterating over all pairs of n elements.
• Geometric series explains why doubling-capacity arrays (ArrayList, Vec) have O(1) amortised insertion: 1 + 2 + 4 + … + n = 2n - 1.
• Harmonic series appears in the analysis of quicksort’s average case and the coupon collector problem.

Pi Notation (Product)#

 n
 Π  f(i)  =  f(1) × f(2) × ... × f(n)
i=1

Factorial: n! = Π_{i=1}^{n} i = 1 × 2 × … × n

Factorials grow extremely fast:

Inequalities#

Inequalities express ordering relationships and are essential for algorithm analysis (Big-O bounds) and constraint satisfaction.

Rules#

The AM-GM Inequality#

The arithmetic mean is always ≥ the geometric mean:

(a + b) / 2 ≥ √(ab)   for a, b ≥ 0

Equality holds when a = b. This is useful for optimisation: it tells you that for a fixed sum, the product is maximised when all terms are equal.

Application: Given a fixed memory budget split between cache and buffer, equal allocation maximises the product of their sizes — relevant when the performance benefit is proportional to the product.

Triangle Inequality#

|a + b| ≤ |a| + |b|

Generalised to metrics and distances, this is the fundamental property that makes algorithms like A* search correct.

Absolute Value and Floor/Ceiling#

Absolute Value#

|x| = x   if x ≥ 0
|x| = -x  if x < 0

Properties:

• |ab| = |a| × |b|
• |a + b| ≤ |a| + |b| (triangle inequality)
• |a - b| represents the distance between a and b on the number line

Floor and Ceiling#

Floor/Ceiling in Programming#

# Python
import math
math.floor(3.7)   # 3
math.ceil(3.2)    # 4
3.7 // 1          # 3.0 (floor division)

# Integer division IS floor division for positive numbers:
7 // 2            # 3 = ⌊7/2⌋

# But NOT for negative numbers in all languages:
# Python: -7 // 2 = -4 (floor)
# C/Java: -7 / 2  = -3 (truncation toward zero)

Common Uses#

Key Takeaways#

• Algebra provides the rules for manipulating equations — the same rules you use when deriving complexity bounds or solving configuration constraints.
• Exponents model explosive growth (brute-force search, resource consumption). Logarithms tame them by measuring “how many times do I halve?”
• Summation formulas (Σ i = n(n+1)/2, geometric series) directly explain algorithm complexity.
• Floor and ceiling functions appear in every pagination, tree height, or bit-width calculation.
• Master the logarithm rules — they are the single most useful algebraic tool in computer science.