Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Binary search complexity

  1. Sep 17, 2011 #1
    i found the recursive relation which is T(n) = 1 + t(n/2)

    after a couple of substitutions i found the pattern which is T(n) = 2i-1 + T(n/ 2i)

    i chose i = log2 n and then when i plugged it in i got

    T(n) - 2log2(n -1) + T(1)

    but doesnt the first part simplify to n-1?

    the complexity of binary search is O(logn)

    where did i mess up?
  2. jcsd
  3. Sep 18, 2011 #2


    Staff: Mentor

    Should be T(n) = 1 + T(n/2), right? Also, in a recursive relationship, there has to be some number at which recursion stops. In that case, it would be T(1), I think, because at some point n/2 will be less than 1.
    Where did this come from? Just above, you have T(n) = 1 + T(n/2).
    How did you get this?
    That's right, assuming the list is in order. Think about a list of 32 numbers. By dividing the list in two, you have two sublists of 16 numbers each. It's pretty easy to tell whether the number you're looking for is in the first list or the second, so you can narrow the search down to on of the 16-element lists.

    Now, divide that list into two 8-element lists. Determine which of these lists the number needs to be in.

    Divide one of the 8-element lists into two 4-element lists, and determine which half the number needs to be in.

    Divide one of the 4-element lists into two 2-element lists, and determine which half the number needs to be in.

    Finally, divide one of the 2-element lists into two single-element list. If the number is present in the first place, it will be in one or the other 1-element list.

    We divided the 32-element list 5 times to get down to a single number. 32 = 25, and log2 32 = 5. The same reasoning can be generalized to lists with n elements.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook