📝 Complexity Theory Worksheet
Topic 2.6: The "Paper Lab" — Manual Analysis & Exam Prep
No code execution today. Just you, paper, and the mathematical foundations of algorithm analysis.
🎓 Professor Ada's Exam Strategy
In interviews and written exams, you won't have an IDE. You'll have a whiteboard or paper. Today's worksheet trains you to:
- Prove Big-O mathematically using constants c and n₀
- Count exact steps in loops without running code
- Trace memory to understand Stack vs. Heap
💡 Grab a pencil and paper. Work through each problem BEFORE checking the solution.
Problem 1: The Mathematical Proof
The Challenge
Prove that T(n) = 4n + 3 is O(n)
Recall the formal definition of Big-O:
f(n) is O(g(n)) if there exist positive constants c and n₀ such that:
f(n) ≤ c · g(n) for all n ≥ n₀
🎯 Professor Ada's Strategy
Think of c as your "budget multiplier" and n₀ as the "starting point" where the inequality becomes true forever.
The Analogy: Imagine you're proving that a growing plant (4n + 3) will always fit under a ceiling (c · n) once it reaches a certain height (n₀).
📝 Your Workspace (Steps to Follow):
- Write down what we need to prove:
4n + 3 ≤ c · n - Handle the constant term: Find a way to express "3" in terms of n
- Choose values for c and n₀ that make the inequality work
- Verify your choice with a specific example (e.g., n = 10)
Problem 2: Exact Step Counting
The Challenge
Given the following Java code, calculate the exact number of times the statement sum++; executes.
public static int nestedSum(int n) {
int sum = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j <= i; j++) {
sum++; // ← How many times does this run?
}
}
return sum;
}🎯 Professor Ada's Hint
The Analogy: Think of this as stacking blocks in a triangular pyramid. The first row has 1 block, the second has 2, the third has 3, and so on.
Baby Steps:
- When i = 0, how many times does j loop? (j goes from 0 to 0)
- When i = 1, how many times does j loop? (j goes from 0 to 1)
- When i = 2, how many times does j loop? (j goes from 0 to 2)
- Find the pattern and sum it up!
📝 Your Workspace:
Create a frequency table:
i = 0: j runs ? times
i = 1: j runs ? times
i = 2: j runs ? times
...
i = n-1: j runs ? times
Total = ?
Problem 3: Memory Trace (Stack vs. Heap)
The Challenge
Given the following Java code, draw the memory state (Stack and Heap):
int x = 5;
int[] y = {1, 2, 3};
String name = "Ada";After these three lines execute, what exists in memory and where?
🎯 Professor Ada's Memory Model
The Analogy: The Stack is like your desk (small, organized, local variables). The Heap is like a warehouse (large, stores objects, referenced by address).
Key Rules:
- Primitives (int, double, boolean) → stored directly on the Stack
- Objects/Arrays → stored on the Heap, Stack holds the reference (address)
- Strings → special objects stored on the Heap (or String Pool)
📝 Your Workspace:
Draw two boxes: Stack and Heap. Place each variable/value:
Stack (Local Variables)
x: ?
y: ?
name: ?
Heap (Objects)
Address 0x1A4: ?
Address 0x2B8: ?
🤔 Quick Check
Where does the variable y live, and where does the array {1, 2, 3} live?
🎓 Worksheet Complete!
You've now practiced the three essential exam skills:
- Mathematical proofs using Big-O definitions
- Exact step counting with arithmetic series
- Memory tracing to understand Stack vs. Heap
💡 Professor Ada's Exam Tip:
These problems appear in technical interviews and university exams. Practice them on paper until you can solve them without checking the solutions. Speed comes from understanding, not memorization!
Keep reading — this lesson marks itself done automatically.