1
$\begingroup$

Was searching for an algorithm that has the worst-case time complexity as $O(\lg(n)).$

Have read that binary-search algorithm, has both the worst-case and best-case time-complexity as $\theta (\lg(n)),$ and am confused, as it seems they miss the underlying point that the data structure, for implementation is important.

Say, for sorted-array it is possible; as also stated in the exercise #2.3-6, of CLRS, 4th edition:

2.3-6
Referring back to the searching problem (see Exercise 2.1-4), observe that if the subarray being searched is already sorted, the searching algorithm can check the midpoint of the subarray against $v$ and eliminate half of the subarray from further consideration. The binary search algorithm repeats this procedure, halving the size of the remaining portion of the subarray each time. Write pseudocode, either iterative or recursive, for binary search. Argue that the worst-case running time of binary search is $\theta(\lg n).$

For reference, have given the exercise #2.1-4, of CLRS, 4th edition:

2.1-4
Consider the searching problem:
Input: A sequence of $n$ numbers $(a_1, a_2, … , a_n)$ stored in array $A[1 : n]$ and a value $x.$
Output: An index $i$ such that x equals $A[i]$ or the special value NIL if x does not appear in $A.$
Write pseudocode for linear search, which scans through the array from beginning to end, looking for $x.$ Using a loop invariant, prove that your algorithm is correct. Make sure that your loop invariant fulfills the three necessary properties.

But, if change the data-structure for implementation, as a tree, i.e. the pointers are there for the parent and child nodes; it is possible that if the data distribution is skewed, then in the worst-case, can have all nodes (elements) in the same branch.
This means that the worst-case time-complexity, of binary-search algorithm is $O(n).$

So, request an algorithm whose worst-case time-complexity is $O(\lg(n)).$

$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

As mentioned in the post, we have to be cautious about data being skewed.

To mitigate this challenge, we use a self-balancing binary tree such as the AVL tree. In AVL tree, the heights of the two child subtrees of any node differ by at most one; if at any time they differ by more than one, rebalancing is done to restore this property. The depth of the tree is of scale $\mathcal{O}(\log n)$ and hence search operation is $\mathcal{O}(\log n)$.

$\endgroup$
6
  • $\begingroup$ So, if AVL tree implementation cannot be done, then sorted-array based implementation is better, than binary tree (based on 3 pointers, to one parent, and 2 children) implementation? $\endgroup$ Commented Jan 2 at 9:21
  • 1
    $\begingroup$ if there is no self-balancing, a binary search tree can end up having $\mathcal{O}(n)$ complexity for search, they might end up being a linked list. $\endgroup$ Commented Jan 2 at 9:34
  • $\begingroup$ Thanks a lot. Please see my post at: math.stackexchange.com/q/5018814/424260 $\endgroup$ Commented Jan 3 at 7:53
  • $\begingroup$ Regarding my last comment above, am unable to understand from the two posts pointed to as being the dupes. Not even am able to understand the comment by @BillDubuque. Am unclear how to ask help. Only way left is to ask doubts in the provided two posts. $\endgroup$ Commented Jan 3 at 9:13
  • $\begingroup$ Adding to my last comment, I do not feel that these two links provide a solution to my problem, even. Only the comment by @BillDubuque, seems to have provided some answer. Though am unclear about it too. $\endgroup$ Commented Jan 3 at 9:50

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.