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.