Divide and conquer recurrence relation

Click For Summary
SUMMARY

The discussion centers on solving the recurrence relation for the number of comparisons needed in a binary search for a set of 64 elements, defined as f(n) = f(n/2) + 2. The correct answer is established as 14 comparisons. Participants emphasize the necessity of an initial condition to solve the recurrence, specifically asking for the number of comparisons required for a set of 2 elements, which is crucial for deriving the solution through iterative substitution.

PREREQUISITES
  • Understanding of recurrence relations
  • Knowledge of binary search algorithms
  • Familiarity with mathematical induction
  • Basic algebraic manipulation skills
NEXT STEPS
  • Study the concept of initial conditions in recurrence relations
  • Learn how to derive solutions for recurrence relations using substitution
  • Explore the efficiency of binary search compared to linear search
  • Investigate the implications of logarithmic time complexity in algorithms
USEFUL FOR

Students in computer science, algorithm enthusiasts, and anyone looking to deepen their understanding of binary search and recurrence relations.

Eng67
Messages
21
Reaction score
0
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!
 
Physics news on Phys.org
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).
 

Similar threads

Differential Equation - Series - Recurrence Relation
  • · Replies 2 ·
Replies
2
Views
2K
How to find upper bound for recurrence relation
  • · Replies 1 ·
Replies
1
Views
2K
Solve the recurrence relation using iteration
  • · Replies 7 ·
Replies
7
Views
2K
Recurrence relations with rabbits pairs
  • · Replies 8 ·
Replies
8
Views
3K
Solving Recurrence Relations in Matlab: A Homework Challenge
  • · Replies 9 ·
Replies
9
Views
5K
What is the recurrence relation for strictly increasing sequences from 1 to n?
  • · Replies 3 ·
Replies
3
Views
3K
Nonhomogeneous recurrence relations
  • · Replies 1 ·
Replies
1
Views
1K
Prove every subset of countable set is either finite or else countable
  • · Replies 1 ·
Replies
1
Views
2K
How to Derive a Recurrence Relation for a Combined Geometric Sequence?
  • · Replies 1 ·
Replies
1
Views
2K
Confusion about definition of a splitting field
  • · Replies 1 ·
Replies
1
Views
2K