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?"

Practice

1.

Which of the following is a reference data type in Java?

int, double, String, boolean

easy

A. String

B. int

C. double

D. boolean

Solution

1. Step 1: Identify primitive vs reference types

   int, double, and boolean are primitive types storing actual values.

2. Step 2: Recognize String as a reference type

   String stores a reference to an object containing text data.

3. Final Answer:

   String -> Option A

4. Quick Check:

   Reference type = String [OK]

Hint: Remember: String is an object, others are primitives [OK]

Common Mistakes:

• Confusing String as primitive
• Thinking int is a reference type
• Assuming all data types are reference types

2.

Which of the following is the correct way to create a new String object in Java?

?

easy

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

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

C. String s = String("hello");

D. String s = new String["hello"];

Solution

1. Step 1: Check correct constructor syntax

   Use 'new' keyword with class name and parentheses: new String("hello")

2. Step 2: Verify case sensitivity and brackets

   Class names are case-sensitive (String, not string), and arrays use [] differently.

3. Final Answer:

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

4. Quick Check:

   Correct object creation syntax = String s = new String("hello"); [OK]

Hint: Use 'new ClassName()' with exact case for objects [OK]

Common Mistakes:

• Using lowercase 'string' instead of 'String'
• Missing 'new' keyword
• Using array brackets [] incorrectly

3.

What will be the output of the following code?

String a = "hello";
String b = a;
b = b + " world";
System.out.println(a);

medium

A. world

B. hello world

C. hello

D. Compilation error

Solution

1. Step 1: Understand reference assignment

   Variable b initially points to the same String object as a ("hello").

2. Step 2: String concatenation creates new object

   b = b + " world" creates a new String object; a still points to original "hello".

3. Final Answer:

   hello -> Option C

4. Quick Check:

   Strings are immutable; original stays same [OK]

Hint: String concatenation creates new object, original unchanged [OK]

Common Mistakes:

• Assuming b changes a's value
• Thinking references share mutable data
• Expecting combined string in a

4.

Find the error in the following code snippet:

String[] arr = new String[3];
arr[0] = "Java";
arr[1] = "Python";
arr[3] = "C++";

medium

A. No error, code runs fine

B. Syntax error in array declaration

C. Missing initialization of array elements

D. Array index out of bounds error

Solution

1. Step 1: Check array size and indices

   Array size is 3, valid indices are 0, 1, 2.

2. Step 2: Identify invalid index usage

   arr[3] accesses index 3 which is outside valid range, causing runtime error.

3. Final Answer:

   Array index out of bounds error -> Option D

4. Quick Check:

   Array indices start at 0, max index = size-1 [OK]

Hint: Array indices go from 0 to length-1 only [OK]

Common Mistakes:

• Using index equal to array length
• Confusing syntax error with runtime error
• Assuming arrays auto-expand

5.

Given the class below, what will be the output?

class Box {
  int length;
  Box(int length) { this.length = length; }
}

public class Test {
  public static void main(String[] args) {
    Box b1 = new Box(5);
    Box b2 = b1;
    b2.length = 10;
    System.out.println(b1.length);
  }
}

hard

A. 10

B. 5

C. Compilation error

D. Runtime error

Solution

1. Step 1: Understand reference assignment for objects

   b2 is assigned the reference of b1, so both point to the same Box object.

2. Step 2: Modify object property via one reference

   Changing b2.length to 10 changes the single Box object's length property.

3. Step 3: Print property via original reference

   Printing b1.length shows 10 because b1 and b2 refer to the same object.

4. Final Answer:

   10 -> Option A

5. Quick Check:

   Object references share same data; change reflects everywhere [OK]

Hint: Object references point to same data; changes affect all refs [OK]

Common Mistakes:

• Thinking b1 and b2 are separate objects
• Expecting original value after change
• Confusing primitives with objects