#### Archived

This topic is now archived and is closed to further replies.

# Efficiency of binary search

This topic is 5749 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

Hi everyone, can anybody tell me what the efficiency of binary search I know that in its worse case it is O (log n) such that f(n) = log2 n. and I know that the best case of the search is O(1) if the data was found immediately. But I am really trying to work out the average case: would that be: f(n) = (log2 n)/2 thanks for ur help Dark Star UK

##### Share on other sites
It doesn''t work that way... O() only cares about how a problem scales as n becomes very large. Constant coefficients and lower order polynomials are all ignored. (e.g. even if something ran in .0001n^2+10000000n time it would still be O(n^2))

As another example, linear search has performance of O(n). Assuming you search for everything in the list exactly once, you''ll do [sum from i = 0 to n of i] comparisons (or n^2/2)... the per-search cost of that is (n^2/2) / n or n/2... but you don''t care about the /2 part because it''s just a constant coefficient.

##### Share on other sites
Oops, my sum is wrong... it should be (n^2 + n) / 2 and per-search cost is (n+1)/2. The +1 is ignored too because it has a lower order than n (^0 as opposed to ^1).

1. 1
Rutin
25
2. 2
3. 3
4. 4
JoeJ
18
5. 5

• 14
• 14
• 11
• 11
• 9
• ### Forum Statistics

• Total Topics
631758
• Total Posts
3002137
×