Question:

Published on: 16 September, 2024

**Find the recurrence relation of binary search and derive the time complexity of binary search.**

Answer:

Binary search is a technique to find a particular element in a sorted list of elements.

Suppose L is the sorted list and d is the element to be searched, lb is the lower bound of the list and ub is the upper bound of the list.

The algorithm is:

Binary_Search(L,lb,ub,d) { K=0 If lb=ub and d=L[lb]…………………………………………….(I) { k=1 exit } Else { mid=(lb+ub)/2 if d=L[mid] { K=1 Exit } If d<L[mid] Binary_Search(l,lb,mid-1,d)………………………………(II) Else Binary_Search(L,mid+1,ub,d)……………………………(III) } If k=1 search is successful Else search is unsuccessful }

** Time complexity of binary search with recurrence relation: **

Best case: If (I) satisfies, which means the element is present at the middle of the list. In that case the time complexity is Ω(1).

Average case: If the element is not present at the middle of the list, then the search will continue in the remaining part of the list depending on the condition (II) and (III). So the list will be divided in to two sublists each of size n/2. In that case, time complexity will be:

T(n)=T(n/2)+ Ω(1)…………………..(a)

Ω(1)=time to compute mid.

According to Master’s theorem, plotting (a) in the form T(n)=aT(n/b)+f(n)

Where , a=number of subproblems

b=size of original problem

n/b=size of each subproblem

f(n)=work done outside recursive calls

Here, a=1,b=2

E=log_{b} a

E=0

Here f(n)=1=n^{0}

So from the 2^{nd} condition of Master’s theorem, we get

T(n)=Θ(log n)

Worst case: The worst case is similar to that of the average case, T(n)=Θ(log n)

Subjects

Trending

**Using greedy strategy, schedule the following jobs with deadline so as to maximize the profit.**

View : 687

16 September, 2024

**Write the string matching algorithm due to Knuth,Moris and Pratt. Analyze its time complexity. **

View : 700

16 September, 2024

Random questions

**Write short notes on the following:**

**Armstrong’s Axioms**

**Outer join**

16 September, 2024

**Discuss Software Maintenance**

16 September, 2024

**Discuss Quality Assurances**

30 May, 2022

**Write the difference between procedural and non-procedural query language.**

16 September, 2024

**Create a Sparse Matrix in C.**

16 September, 2024

**Difference between ISO and CMM standards.**

16 September, 2024

16 September, 2024

**Discuss the different stages of ‘Capability Maturity Model’.**

16 September, 2024