The best case of quick sort helps Student-1 to sort a particular data set of size
'n' in 640 ms. Student-2 also tried the same algorithm on similar data set and
it took him 256 ms in best case to sort a file of size 16. What could be Student-1's file size?
Consider a modification of the insertion sort algorithm, which performs a binary search instead of sequential to find the position where the element to be inserted in each pass of the algorithm. What is the worse case running time of this algorithm?
Time Complexity of insertion sort consist of two part. (1) Cost of comparison (2) Cost of shifting
Using binary search instead of linear search for finding the correct position of element in insertion sort decrease the searching time or Cost of comparison from O(n^2) to O(n \log n), but Cost of shifting still remain O(n^2).
Hence, Total, time complexity still remains O(n^2).
Consider a modification of the insertion sort algorithm, which use link list as data structure to store elements instead of array to reduce the number of shifting of elements while sorting. What is the worse case running time of this algorithm?
Time Complexity of insertion sort consist of two part. (1) Cost of comparison (2) Cost of shifting
Using link list, Cost of shifting can be reduced to O(n) from O(n^2), but Cost of comparison remains O(n^2) as binary search can not be applied in link list. Hence, time complexity remain O(n^2).
Suppose the given array of size n is sorted other than first 10 element and last 50 elements. Find the sorting algorithm which can run faster than other algorithms.
Insertion Sort works faster, because only few elements need to ben inserted in proper places. Merge sort runs longer time compared to quicksort and quicksort runs longer than insertion sort. In this case, bubble sort is slower than insertion sort. So, Insertion sort is faster.
Which of the following cases is definite to give O(n log n) time complexity
always for quick sort to sort the array A[0...n], for any set of values of array
A.
Case 1: Choosing middle element as pivot.
Case 2: Choosing pivot element as (2^0)th element initially followed by
(2^1)th element, followed by (2^2)th element of array A and so on.
Case 3: Choosing median element as pivot.
Case 4: Choosing the pivot element randomly from the array A.
Case 5: Choosing pivot such that the array is portioned into almost two
equal sub arrays
In 6 question bubble and insertion comparison also n-1 then it will all the three expect quick ???