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


Members have full access to the forums. Advertisements are removed for registered users.

Results 1 to 3 of 3

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

  1. #1
    Member
    Join Date
    Apr 2011
    Posts
    32
    Thanks
    20
    Thanked 0 Times in 0 Posts

    Default 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. #2
    Super Moderator Sean4u's Avatar
    Join Date
    Jul 2011
    Location
    Tavistock, UK
    Posts
    637
    Thanks
    5
    Thanked 103 Times in 93 Posts

    Default 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)

  4. #3
    Member
    Join Date
    Apr 2011
    Posts
    32
    Thanks
    20
    Thanked 0 Times in 0 Posts

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

    Thanks Sean!

Similar Threads

  1. Binary datafile and object creation according to binary tag ?
    By loicus in forum Object Oriented Programming
    Replies: 4
    Last Post: October 14th, 2011, 01:00 PM
  2. I need help for this time complexity measurment?
    By lulzimfazlija in forum Algorithms & Recursion
    Replies: 5
    Last Post: September 16th, 2011, 12:17 PM
  3. Binary Numbers
    By Bido in forum Java Theory & Questions
    Replies: 1
    Last Post: January 6th, 2011, 03:54 PM
  4. need help with binary tree
    By vash0047 in forum Java Theory & Questions
    Replies: 5
    Last Post: July 12th, 2010, 08:23 AM
  5. How to convert float and double data types to binary?
    By rosh72851 in forum Java Theory & Questions
    Replies: 1
    Last Post: October 7th, 2008, 10:45 PM