0

Suppose we have a sorted array of unique elements, A[n]. I am trying to find the lower bound for finding a specific element x in the array. I suspect the lower bound to be log_2(n+1).

I tried to use a decision tree to solve this, and indeed we know between 2 elements which is greater, which gives 2 for the base of logarithm, but why all the possible cases n+1?

1
  • If you're looking for a lower bound, it's O(1). The element x could be the first element chosen, thus terminating your algorithm in constant time.
    – Alexander
    May 12, 2017 at 18:34

1 Answer 1

3

The algorithm you're thinking of is Binary Search.

It has a lower bound of O(1), which occurs in its best case: the first element picked is the desired element x. No further searching is required.

It has an upper bound of O(log_2(n)). Every time you pick an element and you decide if you need your next search to move higher or lower, you're eliminating half of the search space. Since each step halves the search space, the question becomes "how many times can I divide the size of the search space in 2, until I reach a single element"? This question of repeated halving is the opposite of repeated doubling (exponentiation), and is solved by a logarithm.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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