The Student Room Group

Best, Average, Worst complexities of a binary search?

If we had a sorted list of 137 elements would the:
Worst case complexity be O=log2(n) = 8
Average case complexity be O=log(n) = 2
Best case complexity be O=n/2=69

Please help I have an exam coming up. Thank you
Reply 1
Avatar for tooosh
tooosh
16
What are you asking? Best case is O(1). You could get lucky and the element you want is in the middle of the list.
Worst case is O(log2(n)) as the number of times you can divide the list up in 2 is the maximum times you'll have to compare elements in a binary search.
Average case is also O(log2(n)). The average number of times you would compare elements in a binary search is halfway between 1 and log2(n), so it's 0.5*log2(n). But the "0.5*" is considered insignificant compared to the rest, so it ends up being O(log2(n)) as well.
Reply 2
Avatar for Planto
Planto
16
Original post by tooosh
The average number of times you would compare elements in a binary search is halfway between 1 and log2(n), so it's 0.5*log2(n). But the "0.5*" is considered insignificant compared to the rest, so it ends up being O(log2(n)) as well.


Your conclusion is correct, but not how you got there. The average number of comparisons in a binary search is, in fact, closer to log⁡2n\log_{2}n than log2n2\frac{log_{2}n}{2}. You can't just assume that the average case is half of the worst case.

http://sce.uhcl.edu/yang/teaching/csci3333spring2011/Average%20case%20analysis%20of%20binary%20search.pdf
(edited 11 years ago)
Reply 3
Avatar for tooosh
tooosh
16
Original post by Planto
Your conclusion is correct, but not how you got there. The average number of comparisons in a binary search is, in fact, closer to log⁡2n\log_{2}n than log2n2\frac{log_{2}n}{2}. You can't just assume that the average case is half of the worst case.

http://sce.uhcl.edu/yang/teaching/csci3333spring2011/Average%20case%20analysis%20of%20binary%20search.pdf


I see. Never really had to consider the average case before.

Quick Reply

Related discussions

Latest

Trending

Trending

Articles for you