Find the recurrence relation of binary search and derive the time complexity of binary search.
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=logb a
E=0
Here f(n)=1=n0
So from the 2nd 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)
Find the recurrence relation of binary search and derive the time complexity of binary search.
Write short notes on
Explain left factoring with suitable example.
Write a C program to check a year is leap year or not.
Write a C program to check a number is even or odd.
Write the rules of DBA.
Write the recursive algorithm to find x^ n.