[Kairiazadi]

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

[tooosh]

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.

[Planto]

(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

[tooosh]

(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.