Reference data types in Java - Time & Space Complexity

Time Complexity: Reference data types

O(n)

Understanding Time Complexity

When working with reference data types in Java, it's important to see how operations on them grow as data size increases.

We want to know how the time needed changes when we use objects and their references.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

class Box {
  int value;
  Box next;
}

void traverse(Box start) {
  Box current = start;
  while (current != null) {
    System.out.println(current.value);
    current = current.next;
  }
}
    

This code walks through a linked list made of Box objects, printing each value.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The while loop that visits each Box object once.
• How many times: Once for every Box in the linked list.

How Execution Grows With Input

As the number of Box objects grows, the loop runs more times, directly matching the list size.

Input Size (n)	Approx. Operations
10	About 10 visits to Box objects
100	About 100 visits
1000	About 1000 visits

Pattern observation: The work grows evenly as the list gets longer.

Final Time Complexity

Time Complexity: O(n)

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

Common Mistake

[X] Wrong: "Accessing objects through references is instant and does not add time."

[OK] Correct: Each step to the next object still takes time, so visiting more objects means more time.

Interview Connect

Understanding how time grows when working with objects and references helps you explain how programs handle data step-by-step.

Self-Check

"What if we changed the linked list to a tree structure? How would the time complexity change?"