# Best, Average, Worst complexities of a binary search? Tweet

Computer Science and ICT discussion, revision, exam and homework help.

Announcements Posted on
Enter our travel-writing competition for the chance to win a Nikon 1 J3 camera 20-05-2013
IMPORTANT: You must wait until midnight (morning exams)/4.30AM (afternoon exams) to discuss Edexcel exams and until 1pm/6pm the following day for STEP and IB exams. Please read before posting, including for rules for practical and oral exams. 28-04-2013
1. 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

2. Re: Best, Average, Worst complexities of a binary search?
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.
3. Re: Best, Average, Worst complexities of a binary search?
(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 than . You can't just assume that the average case is half of the worst case.

http://sce.uhcl.edu/yang/teaching/cs...y%20search.pdf
Last edited by Planto; 04-06-2012 at 10:00.
4. Re: Best, Average, Worst complexities of a binary search?
(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 than . You can't just assume that the average case is half of the worst case.

http://sce.uhcl.edu/yang/teaching/cs...y%20search.pdf
I see. Never really had to consider the average case before.