If an algorithm must make n-1 comparisons to find a certain element, then can we assume that best possible runtime of the algorithm is O(n)? I know that the lower bound for sorting algorithms is nlogn but since we only return the found one element, I figured it would be possible to do better in terms of run time? Thanks!

CodePudding user response：

To find a certain element in an unsorted list you need O(n).

But if you sort the array (takes O(n log n) in general) you can find a certain element in O(log n).

So if you want to find often elements in the same list it is most likely worth to sort the list to then be able to find elements much more efficient.

CodePudding user response：

If your array is unsorted and you find some element in it then in worst case Linear search algorithm make n-1 comparisons and time complexity will be O(n).

But if you want to reduce your time complexity then first sort your array and use Binary search algorithm it is take O(logn) in worst case.

So Binary search algorithm is more efficient then linear search.