CODEWITHSUNDEEP
javaobjectarraylistspace-complexity
Hulk
Hulk

Reputation: 107

ArrayList containing references to TreeNodes, what is the space complexity?

   TreeNode root = new TreeNode(5);
    ArrayList<TreeNode> arr = new ArrayList<TreeNode>();
    for(int i = 0; i < n; i++){
        arr.add(root);
    }

In the above code, a single TreeNode object is added into the ArrayList<TreeNode> arr for n times. I think that arr should have a space complexity of O(1) because it is saving references to single memory block on heap. I am discussing this with my friends and they have different opinion that it might have O(n) complexity. What do you guys think?

Upvotes: 1

Views: 199

Answers (2)

Silviu Burcea
Silviu Burcea

Reputation: 5348

You're saving references, but they are still n references. I think you're actually looking for a memory overhead for storing n objects in an ArrayList. The memory used will probably be dominated by the actual objects, but there is still an array with length n backing that ArrayList holding the references.

Upvotes: 0

dting
dting

Reputation: 39287

The ArrayList still needs to store the reference n times, making it O(n).

ArrayList is backed by an Object[], if you look at the source code 

public boolean add(E e) {
    ensureCapacity(size + 1);  // Increments modCount!!
    elementData[size++] = e;
    return true;
}

Whenever an element is added it added to the backing Object array.

Upvotes: 1

Related Questions