Recursive Algorithm Copying Array vs. Time Complexity

Question

If I am implementing binary search using a recursive algorithm on an array it will be bounded by $O(\log(n))$. However, what will occur if the array is NOT passed by referenced and rather by value. This means that the recursive call will have to first copy the elements of the array (half the original items). Does this mean that the resulting time complexity for a pass-by-value binary search using an array is $O(\log(n)\cdot\log(n))$ or $O(\log(n)^2)$?

Answer 1

The first point is that as in the most binary search implementations we are passing an array with their sub-indices each time, and in the common programming languages, arrays are passed by reference this problem cannot happen.

However, if this copy happened each time this would be $n+\frac{n}{2} + \frac{n}{2^2} + \cdots + \frac{n}{2^{\log(n)}} = \Theta(n)$. Hence, time complexity of this algorithm which copies half of the passed array would be $\Theta(n)$.

Moreover, if the implementation passed the whole of the array each time and control the search using sub-indices, the time complexity would be worse and it would be $\Theta(n\log(n))$, as each time ($\log(n)$) copy the whole of the array with size $n$.