Thread: Binary serarch complexity. Why is it log_2(n) ?

Hey everyone, I am looking at Binary Search Complexity and am stuck on the final result. For binary search, the array is split into half and a check is made to see if the quantity we want is on the left hand or right hand side. So say we had an array of 2^10 elements; that would mean the array would be split 10 times until we can no longer split it further.

So my question is how does the complexity become O(log(n)) using the Big O notation?

Thanks!

You don't have an input whose size is 2^10, you have an input whose size is 1,000. That 2^10 could be mistaken for 2^N, but it isn't: it's N. What you're asking is "how many times must I divide N by 2 until I get a single result (which will be either the one I'm looking for or evidence that it's missing)" or 1 = N / 2^c which can be written 2^c = N and also by taking the log_2 of both sides. That '=' (equals) isn't quite right because what you're interested in in algorithmic complexity is *asymptotic* behaviour: 'big O' notation tells you something about the behaviour of an algorithm as N grows (large). If you ever write something like that yourself, be sure to use the 'proportional' sign or the 'equals-ish' sign. Better yet, ask a mathematician!

Thanks Sean!