Question

#data structures

Give the appropriate execution time efficiency of the following array algorithms using Big-O notation. Assume the size of the array is n.

a)   Linear Search (average case)   ______________________

   b)   Binary Search (worst case)       ______________________

   c)   Insertion Sort (best case)       ______________________

   d)   Insertion Sort (average case)           ______________________

   e)   Quick Sort (average case)           ______________________

Answer 1

Part a)

Linear Search ( Avg Case ) : In this we traverse the array element by element and we compare each with the element that need to be searched . So In average case we say that element is found in between the array . The number of elements traversed are n/2 .

So Time taken in O(n)

Part b)

Binary Search ( Worst Case ) : Here we compare middle element with the element that need to be searched and then if element is less then we traverse the left sub array else right sub array .

So Time Taken is O(logn)

Part c)

Insertion Sort (Best case ) : The best case is when array is already sorted and then we apply insertion sort so no swapping is needed .

Hence Time Taken in O(n)

Part d )

Insertion Sort ( Avg case ) : Average case arrives when some times we have to do so swapping while we do the new insertion while other times we have to swap it with all the elements present to put the its correct position .

So Time Taken in O(n^2)

Part e )

Quick Sort ( Avg case ) :Average case arrives when some times we have elements sorted around the pivot while other times we have to sort them to get the pivot in appropriate position

So Time Taken in O(nlogn)

This is how each algorithm runs in various cases

Thank You

If u like the answer then do Upote it and have any doubt drop in comments