What is average case complexity of binary search?

Answer 1

Average case complexity for Binary search O(log N). (Big O log n)

Habibur Rahman (https://www.facebook.com/mmhabib89)

BUBT University Bangladesh

http://www.bubt.edu.bd/

Answer 2

The average cost of a successful search is about the same as the worst case where an item is not

found in the array, both being roughly equal to log N.

So, the average and the worst case cost of binary search, in big-O notation, is O(log N)

Answer 3

That depends on the list size an how often a search is made for a non existent list item. Doubling the list size from 1024 to 2048 will only add one more iteration to the search in a worst case scenario. This holds true for each time the list is doubled. What may not be evident is that a binary search gets more efficient as the list gets bigger (not to confused with quicker).

Answer 4

The best case complexity is O(1) i.e if the element to search is the middle element. The average and worst case time complexity are O(log n).