1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
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

    HallsofIvy

    User Avatar
    Staff Emeritus
    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).
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Divide and conquer recurrence relation
  1. Recurrence Relation (Replies: 1)

  2. Recurrence relations (Replies: 1)

  3. Recurrence Relations (Replies: 4)

  4. Recurrence relation (Replies: 2)

  5. Recurrence relation (Replies: 5)

Loading...