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

• user16034: How do you obtain this $\log^2(n)$ ?
• user16034: 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 !

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

• delhics: Beautifully explained, thank you for the clarification.
• Ilya Serbis: Why does $n+\frac{n}{2} + \frac{n}{2^2} + \cdots + \frac{n}{2^{\log(n)}}$ equal $\Theta(n)$ but not the $\Theta(n\log(n))$? There are $\log(n)$ summands in the sequence.
• OmG: @IlyaSerbis Because $n + \frac{n}{2} + \frac{n}{2^2} + \ldots + \frac{n}{2^{\log(n)}} = n\left(1 + \frac{1}{2} + \frac{1}{2^2} + \ldots + \frac{1}{2^{\log(n)}}\right),ドル and the phrase of 1ドル + \frac{1}{2} + \frac{1}{2^2} + \ldots + \frac{1}{2^{\log(n)}}$ is a geometric series with a common ratio of $\frac{1}{2}$ such that for large $n,ドル it will goes to 2ドル$ which is a constant.