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)
Using greedy strategy, schedule the following jobs with deadline so as to maximize the profit.
Write the string matching algorithm due to Knuth,Moris and Pratt. Analyze its time complexity.
Write short notes on the following:
Discuss Software Maintenance
Discuss Quality Assurances
Write the difference between procedural and non-procedural query language.
Create a Sparse Matrix in C.
Difference between ISO and CMM standards.
Discuss the different stages of ‘Capability Maturity Model’.
