Data Structures and Algorithms - Old Questions
12. Explain efficiency of
a) Binary Searching
b) Quick sort
Answer
AI is thinking...
a) Binary Searching
Algorithm for Binary Searching:
BinarySearch(A,l,r, key)
{
if(l= = r)
{
if(key = = A[l])
return l+1; //index starts from 0
else
return 0;
}
else
{
m = (l + r) /2 ;
if(key = = A[m])
return m+1;
else if (key < A[m])
return BinarySearch(l, m-1, key) ;
else
return BinarySearch(m+1, r, key) ;
}
}
Efficiency:
From the above algorithm we can say that the running time of the algorithm is
T(n) = T(n/2) + O(1)
= O(logn)
In the best case output is obtained at one run i.e. O(1) time if the key is at middle.
In the worst case the output is at the end of the array so running time is O(logn) time. In the average case also running time is O(logn).
b) Quick Sort
Algorithm for Quick Sort:
QuickSort(A, l, r)
{
if(l<r)
{
p = Partition(A,l,r);
QuickSort(A,l,p-1);
QuickSort(A,p+1,r);
}
}
Partition(A, l, r)
{
x =l; y =r ; p = A[l];
while(x<y)
{
do {
x++;
}while(A[x] <= p);
do {
y--;
} while(A[y] >=p);
if(x<y)
swap(A[x],A[y]);
}
A[l] = A[y];
A[y] = p;
return y; //return position of pivot
}
Efficiency:
Time Complexity:
Best Case: T(n) = O(nlogn)
Worst Case: T(n) = O(n2)
Average Case: T(n) = O(nlogn)