 | This is an archive of past discussions. Do not edit the contents of this page. If you wish to start a new discussion or revive an old one, please do so on the current talk page. |
| Archive 1 | Archive 2 |
Initial discussion
Why do you give the behaviour of binary sort as 1 + log2 N? Surely this is an implementation issue, and depends on exactly what you define as a step? Sjn28
Binary search, you mean. It does depend on what one defines as a step. Usually we want a step to be something which can be performed in time that is bounded above by a constant which depends only on the implementation. In this case each lookup at a particular position in the array counts as a step, and we assume that any such lookup can be done in a guaranteed amount of time. But if we were able to look at many entries in a single step, that would change the efficiency. Seb
Yes, I meant binary search. Sorry, slip of the brain. My point was that I don't think there's much point in saying any more than that the search is O(log N). Specifying something more specific like "3ceil(log_2(n)) + 2" or "2 log_2(n) - 1" is not terribly useful, because (a) you haven't defined what a step is; (b) it depends on exactly which datum you're looking for (you might be lucky); (c) other (unspecified) details of the implementation; but most importantly (d) it doesn't really matter what the constants are. Sjn28
I've updated the page. Tell me if you think it's better. Seb
Thanks! It's much clearer now. Sjn28