CODEWITHSUNDEEP
c++time-complexitybig-o
June
June

Reputation: 345

lower bound of time complexity confusion

Is that possible to prove that a lower bound on the time complexity of any comparison based search algorithm for sorted lists exists? In other words, does any algorithm that takes as input a sorted list and an element and outputs the index of the element in the list (if it appears) have to take a certain number of steps?

Upvotes: 0

Views: 88

Answers (1)

Checkmate
Checkmate

Reputation: 1154

The accepted way to do the particular algorithm you suggested is a binary search https://en.wikipedia.org/wiki/Binary_search_algorithm, which has an average time complexity of O(log N). As noted in a comment above, this algorithm and many like it can be done in a single step under perfect circumstances.

In general, proving that an algorithm is optimized is a difficult problem, which involves either classifying the algorithm or an appeal to triviality. You can find more information here:

https://cstheory.stackexchange.com/questions/1284/problems-that-can-be-used-to-show-polynomial-time-hardness-results

Here:

https://cstheory.stackexchange.com/questions/2038/what-techniques-are-used-for-proving-algorithms-optimal

And here:

https://www.quora.com/Is-there-any-known-way-to-prove-that-an-algorithm-is-optimal

Upvotes: 1

Related Questions