Supplement Lesson

Formal Complexity Theory & Java Memory Model

Filling the Academic Gaps: Memory Architecture, Asymptotic Bounds, and ADT vs Implementation

Phase 1: The Analogy

The Scratchpad vs. The Warehouse

Imagine you're working at a desk. You have a small scratchpad right in front of you for quick notes—phone numbers, today's tasks, temporary calculations. This is your Stack. It's fast to access, but space is limited.

Behind you is a massive warehouse with labeled boxes on shelves. When you need to store something big—like a thousand-item inventory list—you put it in the warehouse and write the box number on your scratchpad. This is your Heap. It's slower to walk back there, but you have tons of space.

Phase 2: Baby Steps Walkthrough

Let's break down how Java uses these two memory areas:

Step 1: Understanding Primitive Types

When you declare int x = 5;, the actual value 5 lives directly on the Stack. It's small enough to fit on your scratchpad. Primitives include int, double, boolean, char—all the simple types.

Step 2: Understanding Reference Types

When you declare int[] arr = new int[1000];, Java creates the actual array in the Heap warehouse. But on your Stack scratchpad, you only write down the "box number" (the memory address). This box number is called a reference.

Step 3: Why This Matters

When you pass an array to a method, you're handing over the box number, not copying the entire warehouse box. This is why modifying an array inside a method affects the original—you're both looking at the same box.

Step 4: What About ArrayList?

An ArrayList stores references to objects on the Heap. It's like having a warehouse box full of sticky notes, where each sticky note has a box number pointing to another item in the warehouse. Even the ArrayList itself is a box in the warehouse.

Phase 3: The Java

// Step 1: Primitive on Stack
int count = 42;              // value 42 lives directly on Stack

// Step 2: Reference on Stack, Object on Heap
int[] numbers = new int[5];  // Stack holds reference
                             // Heap holds actual array [0,0,0,0,0]

// Step 3: Passing references
void modifyArray(int[] arr) {
    arr[0] = 99;             // Changes the Heap box
}
modifyArray(numbers);        // Pass the box number
System.out.println(numbers[0]); // Prints 99 (same box!)

// Step 4: ArrayList - References all the way down
ArrayList<String> names = new ArrayList<>();
names.add("Ada");            // Stack: reference to ArrayList
                             // Heap: ArrayList object
                             // Heap: String "Ada" object
                             // ArrayList stores reference to String

Phase 4: The Socratic Check

Challenge Your Understanding:

• Why can't we store a million-element array directly on the Stack?
• What happens to the Heap object when there are no more references to it?
• If I copy an array reference like int[] copy = original;, do I have two separate arrays?
• Why do we say Java is "pass-by-value" even though arrays seem to change in methods?

Key Takeaways

• Memory: Stack for primitives and references, Heap for objects. Arrays and objects live on the Heap.
• Complexity: Big-O (worst), Big-Omega (best), Big-Theta (average). Focus on dominant terms.
• ADT vs Structure: Interface (what) vs Implementation (how). Enables flexibility and code reuse.

Keep reading — this lesson marks itself done automatically.