1
$\begingroup$

I had an exam today, and there was a question that said:

Based on the definition of binary search algorithm, discuss when the algorithm time will be $O(1)$ and when it will be $O(\log(n))$.

I'm not sure about my answer, but I answered randomly saying that, it can be $O(1)$ when the element I am searching for is at the middle of the array, and it will be $O(\log(n))$ when the element is at the end of the array.

I know my answer might be trivial, but how can I answer a question like this?

$\endgroup$
  • 1
    $\begingroup$ I think the only sensible thing you can say is that if we have an input that bounds the number of iterations by a constant independent of the input size, it is $O(1)$, and otherwise we have the $O(\log n)$ bound. There may be many reasons why binary search could stop after a constant number of iterations, so I don't think there is much more to say here, unless there turns out to be a nice characterisation, of which I am unaware, at least. $\endgroup$ – Discrete lizard Apr 3 at 15:43
  • $\begingroup$ You also get O(1) if all elements in the array have the same value. $\endgroup$ – memo Apr 3 at 15:44
  • $\begingroup$ Any algorithm that is $O(1)$ is also $O(\log n)$ (and $O(50^n)$, etc.), so this question is either tricky or badly worded. Binary search can be implemented either with or without equality tests in-loop; only the with-version is constant time when the query element is in the middle (or more generally, is reached within a bounded number of steps), but I think that's still a reasonable answer. Another sufficient condition for $O(1)$ time would be that the input is bounded in size. $\endgroup$ – j_random_hacker Apr 3 at 15:45
  • $\begingroup$ @memo Or there's exactly one element in the array. $\endgroup$ – Mohamed Magdy Apr 3 at 15:46
3
$\begingroup$

Based on the definition of binary search algorithm, discuss when the algorithm time will be $O(1)$ and when it will be $𝑂(\log n)$.

This is a nice open-ended question to test how well students understand the referred concepts. Here is how I could show my understanding about the conventional binary search.

First, the algorithm time is always $O(\log n)$ in its usually implementation, i.e, an (indexed) sorted array (SA) or a binary search tree (BST) in the RAM model + comparison model (the computation model that is usually used when we talk about binary search). Even if the algorithm happens to find the wanted element in the very first iteration, i.e., comparing the wanted element against the element in the middle of the SA or the root of the BST, it takes $O(\log n)$ time still. Even in the worst time, it takes $O(\log n)$ time still.

Second, the algorithm time will be $O(1)$ when its runs on some particular subsets of the searching problems in some particular ways as illustrated below.

  • The number of elements, i.e., the length of the array or the number of elements in BST is bounded by a constant. In this case, even a linear search algorithm will run in $O(1)$ time. Note that the wanted element may or may not be in the given elements.

    Note this situation is different from the situation when the number of different values of the element (as used in the comparison) is bounded. We may need $\Theta(\log n)$ steps to find the index of a $2$ in an sorted sequence of $n$ numbers all of which are 1, 2, or 3.

  • The wanted element is in the middle of the SA, or in the one-quarter or three-quarter position of the SA, and so on but within a bounded times of iterations. The exact indices of these positions depend on the exact implementation of the binary search. An implementation might check the element at index $(n-1)/2$ first in an array with indices $0,1,\cdots, n$ and odd $n$ or check the element at index $(n+1)/2$ first. The former implementation might need $\Theta(\log n)$ to find the element at index $(n+1)/2$.
  • The wanted element is within a bounded depth away from the root of the BST.
  • We could construct various special set of searching situations where the time for a particular implementation of the algorithm will be $O(1)$ by reverse engineering. Specifying a constant $c$. Searching an array by binary search algorithm. If it ends with $c$ steps, we include that problem instance. All together we will find a set of problem instances where the binary search algorithm will run within $c=O(1)$ steps.

Here is a shorter version that could be used as a reference answer to the question for grading. Again, only the conventional binary search algorithms are considered.

The binary search algorithm always runs in $O(\log n)$ time in the usual computation model.

If the wanted element is among the elements that could be possibly compared within $c$ comparisons for some constant $c$, then the algorithm time is $O(1)$. It happens when the number of total elements is bounded by a constant, when the wanted element is the element in the middle of a sorted array of odd length and when the depth of the wanted element is less than a constant where a binary search tree is used.

$\endgroup$
0
$\begingroup$

I thought for a while and come up with the following. Your question is not completely clear but I am answering on the basis of what I have understood.

Assume that the input array $A$ is given of size $n$. Make a binary tree $\mathcal{T}$ out of the input array $A$. The root(say $r$) of the tree will be the element at index $A[n/2]$. Note that vertex set of the $\mathcal{T}$ will be the elements of the array $A$. Then break the array into two halves and make left half as the left subtree $A[1...n/2-1]$ and the right half $A[n/2+1...n]$ as the right subtree of $\mathcal{T}$ by recursively as defined in the second line. At the end you will have a tree $\mathcal{T}$. Let $x$ be the element which we want to search in an array $A$.

Let $\mathcal{D}(x,r)$ denotes the depth of the element $x$ from the root $r$ of the tree $\mathcal{T}$

Claim: If $\mathcal{D}(x,r) \le \mathcal{O}(1)$ then binary search will stop within $\mathcal{O}(1)$ time.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.