Time and space complexity of passing an array in Java

Question

Suppose I have a recursive function that works on a perfectly balanced binary tree with n nodes and height log(n) and call the function below on the root of the tree.

void printPaths(TreeNode root, int[] array, int depth){
    if (root == null){
        print array;
    }
    array[depth] = root.data;
    printPaths(root.left, array, depth + 1);
    printPaths(root.right, array, depth + 1);
}

array = new int[depthOfTree]
printPaths(root, array, 0);

Let the array be length log(n) (it will store the values along the tree's paths). I know the recursion call stack will be max height log(n). What I'm unsure of is how the "pass-by-value" nature of Java and the Java garbage collection come into play to affect the time and space complexity.

1) What is the time complexity of passing the array to a recursive call? If Java is "pass-by-value," does each recursive call take O(log(n)) to simply copy the array before starting any function execution?

2) What is the upper bound of how many of these array copies are floating around in memory at any one time? My inclination is to say O(log(n)). Does that mean the space complexity is O(log(n)log(n))? I've read in a book that "the space complexity is O(log(n)) since the algorithm will recurse O(log(n)) times and the path parameter is only allocated once at O(log(n)) space during the recursion".

score 5 · Accepted Answer · answered Jul 24 '13 at 05:17

1) What is the time complexity of passing the array to a recursive call? If Java is "pass-by-value," does each recursive call take O(log(n)) to simply copy the array before starting any function execution?

Just O(1). The reference is passed by value. Arrays are reference types (even if the element type of the array is a value type, e.g. for int[]).

So the value of the array expression isn't the array object itself - it's just a reference.

2) What is the upper bound of how many of these array copies are floating around in memory at any one time?

Exactly 1, for the same reason. You've got one array, and each level in the stack has a reference to it.

The only extra memory taken for each recursive step is enough space for the values of the local variables on the stack... which is a constant amount of space per call. With a depth of O(log(N)), that means space complexity of O(log(N)) too.

score 1 · Answer 2 · answered Jul 24 '13 at 05:19

1) What is the time complexity of passing the array to a recursive call? If Java is "pass-by-value," does each recursive call take O(log(n)) to simply copy the array before starting any function execution?

Java doesn't copy the array. In Java, you are passing the reference of Object as arguments in method. So when data of the Object changes, it will get reflected to all the references referring to it.

Time and space complexity of passing an array in Java

2 Answers2