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

Strictly, 2¹⁰ bytes is a kibibyte (KiB). Disk and SSD makers use "KB" for an even 1,000 bytes (and "TB" for 10¹² bytes), which is one reason a "1 TB" drive shows up as about 931 GB in Windows.

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 (ASCII has only 128 characters, so it needs just 7 bits) - 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 (the kind of condition you write in Ch. 4):

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

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

Notice what happened to each comparison: the law flips and/or, and each negated comparison flips too. not (x > 5) is x <= 5 (not x < 5: the case x == 5 has to land somewhere), and not (x == 5) is 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 the same small, fixed number of steps." (For sets and dicts this is the average case; see the table at the end of this section.)

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 on an input only one smaller (like naive Fibonacci, fib(n - 1) + fib(n - 2)): O(2ⁿ), unless memoized. Two calls on halves of the input, as in merge sort, give O(n log n) instead, so look at how much smaller each call's input is, not just how many calls there are.

Big-O in Python Data Structures

*Amortized: occasionally O(n) when the underlying storage has to grow, but O(1) averaged over many operations.

†Average case. Dicts and sets use hashing (Ch. 9); in rare worst cases, when many keys land in the same spot, an operation can degrade to O(n). In everyday code you can count on O(1).

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 (Caesar cipher, a Ch. 7 exercise):

# Shift a capital letter by 3 positions, wrapping X, Y, Z around to A, B, C
position = ord(letter) - ord("A")     # "A" -> 0, ..., "Z" -> 25
shifted = (position + 3) % 26          # "Z": (25 + 3) % 26 = 2
new_letter = chr(shifted + ord("A"))  # 2 -> "C"

Key Property

a % b always returns a value between 0 and b - 1 (inclusive) when b is positive, even when a is negative: -7 % 3 is 2, because -7 = -3 × 3 + 2 (Python's // rounds down, so -7 // 3 is -3). Some other languages, such as C and Java, give -1 here, so this can surprise you when you translate code. Python's rule makes % perfect for wrapping, cycling, and bounding values.

C.5 Basic Logic for Programming

Logical Equivalences You Should Know

The last five rows hold when a is True or False. With other values, and and or hand back one of their operands rather than a bool (0 and True is 0, 5 or False is 5; see Appendix A.2), so the result may not be literally what the middle column shows, though it is equally truthy or falsy.

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).