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

Divide and conquer recurrence relation

  1. Nov 26, 2005 #1
    I am at a loss on how to get the correct answer to this question.

    How many comparisons are needed for a binary search in a set of 64 elements?

    I know the formula f(n) = f(n/2) + 2

    I know the correct answer which is 14.

    No matter what I do I cannot come up with this answer.

    Please help me by showing a couple of steps and I can break down this wall!
  2. jcsd
  3. Nov 26, 2005 #2


    User Avatar
    Science Advisor

    f(n) = f(n/2) + 2
    Yes, that is a recurrance relation. However, every recurrance relation, in order to be unique, must also involve an "initial condition". How many comparisons are needed to search a set containing 2 members?

    You know that f(64)= f(32)+ 2. Okay, what is f(32)? Well, f(32)= f(16)+ 2. What is f(16)? Continue until you "hit bottom"- that is until you reach f(2).
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook