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)
What do you mean by dynamic programming? Write the algorithm of chain matrix multiplication.
Find the recurrence relation of binary search and derive the time complexity of binary search.
Using greedy strategy, schedule the following jobs with deadline so as to maximize the profit.
Write short notes on
Write short notes on:
What do you mean by balancing of DFD? Explain with a suitable example.
Discuss Software Maintenance
What is linear searching?
Describe structured analysis and structured design.
What are the differences between AVL Tree & Binary Search Tree ?
