Fill in the blanks to write a recurrence relation called RecSearch find a specif

Question

Fill in the blanks to write a recurrence relation called RecSearch find a specific value x in a list of size n. You may assume that the list in held in an array called A. Efficiency is not a concern. You must use recursion. The function should return an index (position) of the desired item. Do not make any assumptions about the nature of the list.

RecSearch(A,n,x) = ______________ if ________________= ________________ // _________________ >= 1 (can also index from zero) RecSearch(A,n,x) = ______________ // otherwise

Explanation / Answer

Solution:

RecSearch(A,n,x) = 1 if n= 1 // if n >= 1 (can also index from zero) RecSearch(A,n,x) = RecSearch(A,n/2,x)// otherwise

This is the recurrence relation for binary search which will do the job

and the time complexity will be computed tpo T(n)= O(log n).

If you have any doubt please comment, I'll try to help.

Related Questions

Navigate

• Browse (All)
• Browse F
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.