Question 1 |

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?

40 | |

6 | |

32 | |

64 |

Question 1 Explanation:

Best case of quick sort is c \times n \log n for input size n.

For, for student-1

c \times n \log n = 640

For, for student-2, n=16

c \times 16 \log 16 = 256

c=4

Use this value of c=4 in student-1's equation

4 \times n \log n = 640

n = 32

Click to Join Our Telegram Group for Latest Update of MOCK TEST

Click Here to Practice ALL Previous MOCK TEST FREE

For, for student-1

c \times n \log n = 640

For, for student-2, n=16

c \times 16 \log 16 = 256

c=4

Use this value of c=4 in student-1's equation

4 \times n \log n = 640

n = 32

Click to Join Our Telegram Group for Latest Update of MOCK TEST

Click Here to Practice ALL Previous MOCK TEST FREE

Question 2 |

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?

O(n^2) | |

O(n \ log n). | |

O(n). | |

None of these |

Question 2 Explanation:

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).

Click to Join Our Telegram Group for Latest Update of MOCK TEST

Click Here to Practice ALL Previous MOCK TEST FREE

(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).

Click to Join Our Telegram Group for Latest Update of MOCK TEST

Click Here to Practice ALL Previous MOCK TEST FREE

Question 3 |

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?

O(n^2) | |

O(n \ log n). | |

O(n). | |

None of these |

Question 3 Explanation:

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).

Click to Join Our Telegram Group for Latest Update of MOCK TEST

Click Here to Practice ALL Previous MOCK TEST FREE

(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).

Click to Join Our Telegram Group for Latest Update of MOCK TEST

Click Here to Practice ALL Previous MOCK TEST FREE

Question 4 |

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.

Merge Sort | |

Insertion sort | |

Quick Sort | |

Bubble sort |

Question 4 Explanation:

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.

Click to Join Our Telegram Group for Latest Update of MOCK TEST

Click Here to Practice ALL Previous MOCK TEST FREE

Click to Join Our Telegram Group for Latest Update of MOCK TEST

Click Here to Practice ALL Previous MOCK TEST FREE

Question 5 |

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

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

Only 1 and 4 | |

Only 1, 2 and 3 | |

Only 3 and 5 | |

Only 1, 3 and 4 |

Question 5 Explanation:

Case 1 : In worse case, middle element is smallest or highest element which converts quick sort into worse case.

Case 2 : In worse case, the selected element is smallest or highest element which converts quick sort into worse case.

Case 3 : if median is selected as pivot then both partition size remain same which converts quick sort into best case.

Case 4 : In worse case, randomly selected element is smallest or highest element which converts quick sort into worse case.

Case 5 : If pivot is selected such that the array is partitioned into almost two equal sub arrays then it converts quick sort into best case.

So, Case 3 and 5 is correct.

Click to Join Our Telegram Group for Latest Update of MOCK TEST

Click Here to Practice ALL Previous MOCK TEST FREE

Case 2 : In worse case, the selected element is smallest or highest element which converts quick sort into worse case.

Case 3 : if median is selected as pivot then both partition size remain same which converts quick sort into best case.

Case 4 : In worse case, randomly selected element is smallest or highest element which converts quick sort into worse case.

Case 5 : If pivot is selected such that the array is partitioned into almost two equal sub arrays then it converts quick sort into best case.

So, Case 3 and 5 is correct.

Click to Join Our Telegram Group for Latest Update of MOCK TEST

Click Here to Practice ALL Previous MOCK TEST FREE

There are 5 questions to complete.

In 6 question bubble and insertion comparison also n-1 then it will all the three expect quick ???