what is the tight lower time complexity bound for searching in a sorted array

Question

For example, in sorting the tight lower bound is N*log(N) where N is the size of the array

how about for searching in a sorted array? I think it's log(N) but I'm not 100% sure.

also everything is based on comparisons, no any other external memory than the input array itself can be used

thanks in advance

Answer 1

I'm not quite sure what tight means, but I can give you a proof that O(log n) is the lower complexity bound of the problem.

Problem complexity talks about the complexity of the problem in general instead of algorithm.

There are only three results of comparing an element in the array and the given element:

array[i]=element: stop
array[i]<element: search the first half
array[i]>element: search the second half

This process can be represented by a binary tree. In the best case, the deepth of the tree is O(log n). Therefore we can assert that no algorithm will be faster than O(log n), which is the lower bound on time of the problem.

The upper bound of problem complexity is given by the lowest time complexity of any algorithm solving the problem. There exists Binary Search algorithm whose complexity is O(log n).

As to the search array problem, the upper bound and lower bound coincide, so the problem complexity is O(log n).

Answer 2

The optimal solution for searching a simple sorted array is a Binary Search, which has time complexity O(log₂(N)). The worst case happens when the searched-for element is not in the array, and takes exactly ⌊log₂(N) + 1⌋ iterations. See Binary Search Performance.

I believe you can only talk about "tightness" when referring to the upper AND lower bounds of complexity. Lower bound (big Omega) is generally more difficult to compute, and often not as useful as upper bound (big O). Tight bound (big Theta) takes both upper and lower bounds into account.

Technically the lower bound is Ω(1), because you can find the searched-for element on the first comparison. See Is binary search theta log (n) or big O log(n) for further discussion of the time complexity of binary search.

Answer 3

Yes: the lower bound for searching in a sorted array using only comparisons is o(log n).

For a not-at-all-rigorous proof as to why this is so, imagine the decision tree for any algorithm solving this problem. The number of leaf nodes in the tree is equal to n+1 (one result for each position and a “not found” result). As such, the minimum depth of this tree has to be of the order of log₂ n.