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)$?
$\begingroup$
$\endgroup$
2
-
2$\begingroup$ How do you obtain this $\log^2(n)$ ? $\endgroup$user16034– user160342023-08-23 07:01:18 +00:00Commented Aug 23, 2023 at 7:01
-
$\begingroup$ 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 ! $\endgroup$user16034– user160342023-08-23 07:03:58 +00:00Commented Aug 23, 2023 at 7:03
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
3
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$.
-
1$\begingroup$ Beautifully explained, thank you for the clarification. $\endgroup$delhics– delhics2018-02-05 16:43:19 +00:00Commented Feb 5, 2018 at 16:43
-
$\begingroup$ 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. $\endgroup$Ilya Serbis– Ilya Serbis2025-07-04 13:32:59 +00:00Commented Jul 4 at 13:32
-
$\begingroup$ @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. $\endgroup$OmG– OmG2025-07-04 14:02:27 +00:00Commented Jul 4 at 14:02