Appendix C: Mathematical Foundations

You don't need to be a math whiz to succeed in CS1. This appendix covers the mathematical concepts that appear in this textbook — binary numbers, Boolean algebra, Big-O notation, modular arithmetic, and logic — at an intuitive level. If you're comfortable with these topics already, skim through; if any are new, work through the examples.

C.1 The Binary Number System

Why Binary Matters

Computers store everything — numbers, text, images, music, instructions — as sequences of 0s and 1s. Each 0 or 1 is a bit (binary digit). A group of 8 bits is a byte. Understanding binary helps you grasp how computers represent data at the lowest level, why certain limits exist (like the maximum value of an integer in some languages), and why bitwise operations work the way they do.

Positional Notation

You already understand positional notation — you use it every day in decimal (base 10). The number 347 means:

3 × 10² + 4 × 10¹ + 7 × 10⁰
= 3 × 100 + 4 × 10  + 7 × 1
= 300     + 40       + 7
= 347

Binary (base 2) works identically, but each position represents a power of 2 instead of 10. The binary number 1011 means:

1 × 2³ + 0 × 2² + 1 × 2¹ + 1 × 2⁰
= 1 × 8 + 0 × 4  + 1 × 2  + 1 × 1
= 8      + 0      + 2      + 1
= 11 (in decimal)

Powers of 2 — Know These

Converting Decimal to Binary

To convert a decimal number to binary, repeatedly divide by 2 and record the remainders (reading them bottom to top):

Example: Convert 25 to binary.

Reading remainders bottom to top: 11001

Verification: 1×16 + 1×8 + 0×4 + 0×2 + 1×1 = 16 + 8 + 1 = 25

Binary in Python

Python supports binary literals and conversions directly:

# Binary literal (prefix 0b)
x = 0b11001           # decimal 25

# Convert decimal to binary string
bin(25)               # '0b11001'

# Convert binary string to decimal
int('11001', 2)       # 25

# Hexadecimal (base 16) — related to binary (each hex digit = 4 bits)
hex(255)              # '0xff'
0xFF                  # 255

Why 8 Bits Matter

With 8 bits (one byte), you can represent 2⁸ = 256 different values (0 through 255 for unsigned integers). This is why: - ASCII characters fit in one byte (128 values needed) - RGB color values range from 0 to 255 - An "unsigned byte" can't exceed 255

Python's integers have no fixed size limit — they grow as needed — but understanding fixed-width binary representation matters when working with files, network protocols, image data, and other languages.

C.2 Boolean Algebra

The Three Basic Operations

Boolean algebra operates on just two values: True and False (or 1 and 0). Three operations combine them:

AND — both must be true:

OR — at least one must be true:

NOT — inverts the value:

Operator Precedence

In compound expressions, evaluate in this order: not first, then and, then or.

# Example: not True or False and True
# Step 1: not True         → False
# Step 2: False and True   → False
# Step 3: False or False   → False

When in doubt, use parentheses to make your intent explicit:

if (age >= 18 and has_license) or is_emergency:

De Morgan's Laws

These two laws let you simplify negations of compound expressions. They are among the most useful rules in programming:

Law 1: not (A and B) is equivalent to (not A) or (not B)

Law 2: not (A or B) is equivalent to (not A) and (not B)

In plain English: - "It's not the case that both A and B are true" means "at least one of them is false." - "It's not the case that either A or B is true" means "neither is true."

Practical example (Ch. 4):

# These two conditions are equivalent:
if not (temperature > 100 or humidity > 80):
    print("Comfortable")

if temperature <= 100 and humidity <= 80:
    print("Comfortable")

De Morgan's laws are why not (x > 5) simplifies to x <= 5, and not (x == 5) simplifies to x != 5.

Short-Circuit Evaluation

Python evaluates Boolean expressions lazily: - A and B — if A is false, B is never evaluated (the result is already false). - A or B — if A is true, B is never evaluated (the result is already true).

This is useful for guarding against errors:

# Safe: if the list is empty, Python never evaluates lst[0]
if len(lst) > 0 and lst[0] == target:
    print("Found at index 0")

C.3 Big-O Notation

The Intuition

Big-O notation describes how the running time of an algorithm grows as the input size grows. It answers the question: "If I double the input, how much longer will it take?"

Big-O ignores constant factors and lower-order terms. We don't care whether an algorithm takes 3n or 5n steps — we care that it grows linearly with n. The notation captures the shape of the growth curve, not the exact numbers.

The Common Classes

Listed from fastest to slowest growth:

O(1) — Constant Time. The operation takes the same amount of time regardless of input size.

Examples: looking up an item by index in a list (lst[5]), checking membership in a set (x in my_set), accessing a dictionary value by key (d["name"]).

Intuition: "No matter how big the dataset, this takes one step."

O(log n) — Logarithmic Time. The operation cuts the problem in half each step.

Example: binary search (Ch. 19). Searching 1,000 items takes about 10 steps. Searching 1,000,000 items takes about 20 steps.

Intuition: "Doubling the input adds just one more step."

O(n) — Linear Time. The operation touches each element once.

Examples: linear search (Ch. 19), summing a list, printing every element, finding the maximum.

Intuition: "Double the input, double the time."

O(n log n) — Linearithmic Time. The operation does "log n work" for each of "n elements."

Examples: merge sort (Ch. 19), Python's built-in sorted() and .sort() (Timsort).

Intuition: "A bit worse than linear, but much better than quadratic."

O(n²) — Quadratic Time. The operation involves a nested loop over the data.

Examples: selection sort (Ch. 19), insertion sort (Ch. 19), checking all pairs in a list.

Intuition: "Double the input, quadruple the time."

O(2ⁿ) — Exponential Time. The operation doubles with each additional input element.

Example: naive recursive Fibonacci without memoization (Ch. 18), brute-force subset generation.

Intuition: "Adding one more item doubles the total work. Gets impossibly slow fast."

Growth Rate Comparison

For n = 1,000 (one thousand elements):

This is why algorithm choice matters. An O(n²) algorithm that works fine on 100 items becomes painfully slow on 10,000 items and completely unusable on 1,000,000.

How to Determine Big-O (Informal)

1. Single loop over n items: O(n)
2. Nested loop, both over n items: O(n²)
3. Loop that halves the range each iteration: O(log n)
4. Single loop containing a halving loop: O(n log n)
5. No loops, just direct operations: O(1)
6. Recursive function that calls itself twice: O(2ⁿ) (unless memoized)

Big-O in Python Data Structures

*Amortized — occasionally O(n) when the underlying structure resizes, but O(1) on average.

This table explains why Chapter 9 emphasizes choosing dictionaries or sets over lists when you need fast lookups.

C.4 Modular Arithmetic

The Modulo Operator

The modulo operator (%) returns the remainder after integer division:

17 % 5 = 2    (because 17 = 3 × 5 + 2)
10 % 3 = 1    (because 10 = 3 × 3 + 1)
8 % 4 = 0     (because 8 = 2 × 4 + 0)
7 % 10 = 7    (because 7 = 0 × 10 + 7)

Applications in This Textbook

Checking divisibility (Ch. 4, 5):

if n % 2 == 0:
    print("Even")
else:
    print("Odd")

if year % 4 == 0 and (year % 100 != 0 or year % 400 == 0):
    print("Leap year")

Extracting digits (Ch. 5):

number = 12345
last_digit = number % 10       # 5
remaining = number // 10       # 1234

Cycling through values (Ch. 5):

# Rotate through 0, 1, 2, 0, 1, 2, ...
for i in range(10):
    print(i % 3, end=" ")     # 0 1 2 0 1 2 0 1 2 0

Time conversions (Ch. 3):

total_seconds = 3661
hours = total_seconds // 3600          # 1
minutes = (total_seconds % 3600) // 60 # 1
seconds = total_seconds % 60           # 1

Wrapping around (Ch. 7 — Caesar cipher):

# Shift a letter by 3 positions, wrapping Z back to C
shifted = (position + 3) % 26

Key Property

a % b always returns a value between 0 and b - 1 (inclusive) when b is positive. This makes it perfect for wrapping, cycling, and bounding values.

C.5 Basic Logic for Programming

Logical Equivalences You Should Know

Building Truth Tables

When debugging complex conditions, build a truth table. List all combinations of inputs and trace the output:

Example: (A or B) and (not C)

This is exactly the process you use in Chapter 4 when debugging conditional logic.

Simplifying Conditions

When your if statement has gotten unwieldy, look for these simplification opportunities:

1. Eliminate redundant checks: python # Before if x > 0 and x > 5: # x > 0 is redundant — if x > 5, then x > 0 # After if x > 5:

2. Use chained comparisons: python # Before if x >= 0 and x <= 100: # After if 0 <= x <= 100:

3. Return Boolean values directly: python # Before if score >= 90: return True else: return False # After return score >= 90

4. Apply De Morgan's laws to simplify negations: python # Before if not (age < 18 or not has_id): # After (apply De Morgan, simplify double negation) if age >= 18 and has_id:

C.6 Summary of Mathematical Notation Used in This Book

You do not need calculus, linear algebra, or statistics for this course. If you continue to CS2 or an algorithms course, you'll encounter more formal treatments of Big-O (including Big-Omega and Big-Theta), recurrence relations, and proof techniques — but for CS1, the intuitive understanding in this appendix is sufficient.

For a deeper treatment of discrete mathematics for computer science, see Rosen, "Discrete Mathematics and Its Applications" or Lehman, Leighton, and Meyer, "Mathematics for Computer Science" (freely available from MIT OpenCourseWare).