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 the string matching algorithm due to Knuth,Moris and Pratt. Analyze its time complexity.
Write Short Note on Rapid Application Development
Difference between Statement coverage and Branch coverage.
What is Resource management?
