Heap memory in Java - Time & Space Complexity

Time Complexity: Heap memory

O(n)

Understanding Time Complexity

When working with heap memory in Java, it's important to understand how the program's speed changes as it uses more memory.

We want to see how the time to allocate and manage memory grows as the program runs.

Scenario Under Consideration

Analyze the time complexity of creating objects stored in heap memory.

public class Example {
    public static void main(String[] args) {
        int n = 1000;
        MyObject[] arr = new MyObject[n];
        for (int i = 0; i < n; i++) {
            arr[i] = new MyObject(i);
        }
    }
}

class MyObject {
    int value;
    MyObject(int value) {
        this.value = value;
    }
}
    

This code creates an array of objects, each stored in heap memory, one by one.

Identify Repeating Operations

Look for repeated actions that take time.

• Primary operation: Creating a new object in each loop cycle.
• How many times: The loop runs n times, creating n objects.

How Execution Grows With Input

As the number of objects n increases, the time to create them grows directly with n.

Input Size (n)	Approx. Operations
10	10 object creations
100	100 object creations
1000	1000 object creations

Pattern observation: Doubling n doubles the work because each object creation takes roughly the same time.

Final Time Complexity

Time Complexity: O(n)

This means the time to create objects grows in a straight line with the number of objects.

Common Mistake

[X] Wrong: "Creating objects in heap memory is instant and does not affect program speed."

[OK] Correct: Each object creation takes time and memory allocation, so more objects mean more time spent.

Interview Connect

Understanding how heap memory allocation affects time helps you write efficient programs and answer questions about memory use and speed.

Self-Check

"What if we reused objects instead of creating new ones each time? How would the time complexity change?"

Practice

1. Which of the following best describes heap memory in Java?

easy

A. It stores method call information and local variables.

B. It stores primitive variables like int and double.

C. It stores all objects created using new keyword.

D. It stores the Java bytecode instructions.

Solution

1. Step 1: Understand what heap memory stores

   Heap memory is used to store objects created dynamically using the new keyword in Java.

2. Step 2: Differentiate from other memory areas

   Primitive variables and method calls are stored on the stack, not heap. Bytecode is stored in method area, not heap.

3. Final Answer:

   It stores all objects created using new keyword. -> Option C

4. Quick Check:

   Heap memory = objects from new [OK]

Hint: Heap = objects created with new keyword [OK]

Common Mistakes:

• Confusing stack with heap memory
• Thinking primitives are stored in heap
• Mixing method area with heap

2. Which of the following Java statements correctly creates an object stored in heap memory?

easy

A. String s = new String("hello");

B. int x = 5;

C. double y = 3.14;

D. boolean flag = true;

Solution

1. Step 1: Identify object creation syntax

   Objects in Java are created using the new keyword, which allocates memory on the heap.

2. Step 2: Check each option

   String s = new String("hello"); uses new String("hello"), which creates a String object on the heap. Other options declare primitives stored on the stack.

3. Final Answer:

   String s = new String("hello"); -> Option A

4. Quick Check:

   Object creation uses new keyword [OK]

Hint: Look for 'new' keyword to spot heap allocation [OK]

Common Mistakes:

• Assuming primitives use heap
• Confusing string literals with new String()
• Ignoring that only new creates heap objects

3. What will be the output of the following Java code?

class Test {
  public static void main(String[] args) {
    String a = new String("abc");
    String b = a;
    a = null;
    System.out.println(b);
  }
}

medium

A. null

B. Runtime exception

C. Compilation error

D. abc

Solution

1. Step 1: Understand object references and heap

   Variable a points to a String object "abc" in heap. Then b is assigned the same reference.

2. Step 2: Analyze effect of setting a to null

   Setting a = null removes one reference, but b still points to the object, so it remains accessible.

3. Step 3: Print b

   Printing b outputs the string "abc".

4. Final Answer:

   abc -> Option D

5. Quick Check:

   Reference b still points to "abc" [OK]

Hint: Nulling one reference doesn't delete object if others exist [OK]

Common Mistakes:

• Assuming object is deleted when one reference is null
• Confusing references with objects
• Expecting null output incorrectly

4. Identify the error in the following Java code related to heap memory usage:

public class Demo {
  public static void main(String[] args) {
    int[] arr = new int[5];
    arr = null;
    System.out.println(arr.length);
  }
}

medium

A. No error, prints 5

B. NullPointerException at runtime

C. Compilation error due to null assignment

D. Array size becomes zero

Solution

1. Step 1: Understand array creation and null assignment

   The array is created on heap with size 5, then arr reference is set to null.

2. Step 2: Analyze printing arr.length

   Since arr is null, accessing arr.length causes a NullPointerException at runtime.

3. Final Answer:

   NullPointerException at runtime -> Option B

4. Quick Check:

   Accessing member on null reference throws exception [OK]

Hint: Accessing null reference causes NullPointerException [OK]

Common Mistakes:

• Thinking null assignment causes compile error
• Expecting array length to print after null
• Confusing null with empty array

5. Consider this Java code snippet:

class Node {
  int value;
  Node next;
  Node(int val) { value = val; }
}

public class Test {
  public static void main(String[] args) {
    Node n1 = new Node(1);
    Node n2 = new Node(2);
    n1.next = n2;
    n2.next = n1;
    n1 = null;
    n2 = null;
    // What happens to the Node objects in heap?
  }
}

What happens to the two Node objects in heap after n1 and n2 are set to null?

hard

A. Both objects become unreachable and eligible for garbage collection.

B. Objects remain in heap because they reference each other, preventing garbage collection.

C. Only n1 object is collected, n2 remains.

D. Objects cause a memory leak and crash the program.

Solution

1. Step 1: Analyze object references after null assignments

   Both n1 and n2 references are set to null, so no external references point to these objects.

2. Step 2: Understand garbage collection with cyclic references

   Even though the two objects reference each other, Java's garbage collector detects unreachable cycles and frees them.

3. Final Answer:

   Both objects become unreachable and eligible for garbage collection. -> Option A

4. Quick Check:

   Unreachable objects, even cyclic, are collected [OK]

Hint: Java GC collects unreachable cyclic objects too [OK]

Common Mistakes:

• Thinking cyclic references prevent garbage collection
• Assuming memory leak without external references
• Confusing references with reachability