Welcome to the Java Programming Forums

The professional, friendly Java community. 21,500 members and growing!

The Java Programming Forums are a community of Java programmers from all around the World. Our members have a wide range of skills and they all have one thing in common: A passion to learn and code Java. We invite beginner Java programmers right through to Java professionals to post here and share your knowledge. Become a part of the community, help others, expand your knowledge of Java and enjoy talking with like minded people. Registration is quick and best of all free. We look forward to meeting you.

>> REGISTER NOW TO START POSTING

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

1. ## 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!

2. ## Re: Binary serarch complexity. Why is it log_2(n) ?

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!

3. ## The Following User Says Thank You to Sean4u For This Useful Post:

u-will-neva-no (March 17th, 2012)

Thanks Sean!