Ch.7: Math Foundations

[Math] Logarithm

log_b(n) = x means bˣ = n. Example: log₂(8) = 3, because 2³ = 8.
```python
import math

print(math.log2(8)) # → 3.0
print(math.log(100, 10)) # → 2.0
```

[Math] What does log₂(n) mean in plain words?

The number of times you can halve n before reaching 1. That's why halving algorithms like binary search are O(log n).
```python
def halvings(n):
steps = 0
while n > 1:
n //= 2
steps += 1
return steps

print(halvings(1024)) # → 10
print(halvings(1000)) # → 9 ← floor(log₂ 1000)
```

[Math] What is log₂(1024)?

10, because 2¹⁰ = 1024.

[Math] Handy powers of 2

2¹⁰ ≈ 1,000 (1,024). 2²⁰ ≈ 1 million. 2³⁰ ≈ 1 billion. So log₂ of a billion is about 30.
```python
print(2 ** 10, 2 ** 20) # → 1024 1048576
```

[Math] Exponent rules

aᵐ · aⁿ = aᵐ⁺ⁿ. (aᵐ)ⁿ = aᵐⁿ. a⁰ = 1.

[Math] Logarithm rules

log(ab) = log a + log b. log(a/b) = log a − log b. log(aᵏ) = k · log a.

[Math] Change of base, and why log bases don't matter in Big-O

log_b(n) = log(n) / log(b). Changing the base only multiplies by a constant, so O(log₂ n) = O(log₁₀ n) = O(log n).
```python
import math

for n in [10, 1000, 10 ** 6]:
print(round(math.log2(n) / math.log10(n), 4)) # → 3.3219, then 3.3219, then 3.3219 ← always the same constant
```

[Math] Arithmetic series: 1 + 2 + 3 + ... + n

n(n + 1) / 2, which is O(n²). It's the cost of a nested loop where the inner loop runs i times.
```python
n = 100
print(sum(range(1, n + 1)), n * (n + 1) // 2) # → 5050 5050

count = 0
for i in range(n):
for j in range(i):
count += 1
print(count) # → 4950 ← n(n − 1)/2 inner-loop runs, so O(n²)
```

[Math] Geometric series: 1 + 2 + 4 + ... + 2ᵏ

2ᵏ⁺¹ − 1. The last term is about half the total, which shows up in heap and tree analysis.
```python
k = 10
print(sum(2 ** i for i in range(k + 1)), 2 ** (k + 1) - 1) # → 2047 2047
```

[Math] Summation notation (Σ)

Σᵢ₌₁ⁿ i means "add i for every i from 1 to n," i.e., 1 + 2 + ... + n.
```python
print(sum(i for i in range(1, 6))) # → 15 ← Σ i for i = 1..5
```

[Math] Floor and ceiling

floor(x) rounds down, ceil(x) rounds up: floor(3.7) = 3, ceil(3.2) = 4. In Python, `//` is floor division and `math.ceil()` rounds up.
```python
import math

print(math.floor(3.7), math.ceil(3.2)) # → 3 4
print(7 // 2, -7 // 2) # → 3 -4
```

[Math] Modulo (%)

The remainder after division: 17 % 5 = 2. Used for hash table indexes, cycling through positions, and checking even/odd (`n % 2 == 0`).
```python
print(17 % 5) # → 2
print(12 % 2 == 0) # → True ← even
print([i % 3 for i in range(7)]) # → [0, 1, 2, 0, 1, 2, 0] ← wraps around
```

[Math] Growth rates, slowest to fastest

1 < log n < n < n log n < n² < n³ < 2ⁿ < n!
```python
import math

n = 16
print(math.log2(n), n, n * math.log2(n), n ** 2, 2 ** n) # → 4.0 16 64.0 256 65536
```

[Math] Proof by induction

Prove a statement for the base case (e.g., n = 1), then prove that if it holds for n it also holds for n + 1. It's the math version of recursion.

[Math] Why does halving the input give a log, and doubling the calls give an exponent?

Halving n each step takes log₂(n) steps. Doubling the number of calls each level gives 2ⁿ calls after n leve