Divide and conquer recurrence relation

In summary, the conversation discusses the formula for a binary search and the question of how many comparisons are needed for a set of 64 elements. The formula for the binary search is f(n) = f(n/2) + 2, and the correct answer for 64 elements is 14. The conversation also mentions the importance of an initial condition in a recurrance relation and suggests breaking down the problem into smaller sets until reaching the initial condition.
  • #1
Eng67
21
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
  • #2
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).
 

Related to Divide and conquer recurrence relation

1. What is a divide and conquer recurrence relation?

A divide and conquer recurrence relation is a mathematical expression that describes the relationship between the time or space complexity of a divide and conquer algorithm and the size of the problem being solved. It is often used to analyze the efficiency and performance of these types of algorithms.

2. How is a divide and conquer recurrence relation different from a regular recurrence relation?

A divide and conquer recurrence relation differs from a regular recurrence relation in that it takes into account the "divide and conquer" approach of breaking a problem into smaller subproblems and solving them recursively. This results in a different mathematical expression and can provide more accurate analysis of the algorithm's efficiency.

3. What is the general form of a divide and conquer recurrence relation?

The general form of a divide and conquer recurrence relation is T(n) = aT(n/b) + f(n), where T(n) represents the time or space complexity of the algorithm for a problem size of n, a is the number of subproblems created, n/b is the size of each subproblem, and f(n) is the time or space complexity of combining the solutions of the subproblems.

4. How do you solve a divide and conquer recurrence relation?

To solve a divide and conquer recurrence relation, you can use the Master Theorem or the Substitution Method. These methods involve analyzing the value of a, b, and f(n) in the general form of the relation and using a mathematical formula to determine the overall complexity of the algorithm.

5. What are the benefits of using a divide and conquer recurrence relation in algorithm analysis?

Using a divide and conquer recurrence relation in algorithm analysis can provide a more accurate understanding of the efficiency and performance of the algorithm, as it takes into account the divide and conquer approach. This can help in making informed decisions about which algorithm to use for a particular problem and can also aid in optimizing the algorithm for better performance.

Similar threads

Prove every subset of countable set is either finite or else countable
    • Calculus and Beyond Homework Help
Replies
1
Views
530
Differential Equation - Series - Recurrence Relation
    • Calculus and Beyond Homework Help
Replies
2
Views
1K
How to find upper bound for recurrence relation
    • Calculus and Beyond Homework Help
Replies
1
Views
2K
Solve the recurrence relation using iteration
    • Calculus and Beyond Homework Help
Replies
7
Views
1K
Recurrence relations with rabbits pairs
    • Calculus and Beyond Homework Help
Replies
8
Views
2K
Solving Recurrence Relations in Matlab: A Homework Challenge
    • Calculus and Beyond Homework Help
Replies
9
Views
5K
I The general notion of a recurrence relation
    • Set Theory, Logic, Probability, Statistics
Replies
18
Views
2K
I A nonlinear recurrence relation
    • General Math
Replies
12
Views
2K
What is the recurrence relation for strictly increasing sequences from 1 to n?
    • Calculus and Beyond Homework Help
Replies
3
Views
2K
Nonhomogeneous recurrence relations
    • Calculus and Beyond Homework Help
Replies
1
Views
1K

Hot Threads

Recent Insights

Back
Top