# Recursive Algorithm Copying Array vs. Time Complexity

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)$?

• How do you obtain this $\log^2(n)$ ?
– user16034
Aug 23, 2023 at 7:01
• Passing the array by value is a total waste. Just the initial call will take $O(n)$ for the copy. Better perform a non-recursive linear search !
– user16034
Aug 23, 2023 at 7:03

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$.