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

Homework Help: 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

    HallsofIvy

    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