Consider the Quick sort algorithm in which the partitioning procedure splits elements into two sub-arrays and each sub-array contains at least one-fourth of the elements. Let T(n) be the number of comparisons required to sort array of n elements. Then T(n)<=?
A. T(n) <= 2 T(n/4) + cn
B. T(n) <= T(n/4) + T(3n/4) + cn
C. T(n) <= 2 T(3n/4) + cn
D. T(n) <= T(n/3) + T(3n/4) + cn
Select an option to see the answer and solution.
What is the time complexity for a given pancake sort given it undergoes "n" flip operations?
A. O(n)
B. O(n2 )
C. O(n3 )
D. O(2n)
Select an option to see the answer and solution.
What is the average time complexity of counting sort?
A. O(n)
B. O(n+k) k=range of input
C. O(n2 )
D. O(n log n)
Select an option to see the answer and solution.
What is the best case time complexity of cocktail sort?
A. O(n)
B. O(n log n)
C. O(n2 )
D. O(log n)
Select an option to see the answer and solution.
What is the best case time complexity of permutation sort?
A. O(n2 )
B. O(n)
C. O(n log n)
D. O(1)
Select an option to see the answer and solution.
What is the alternate name of bucket sort?
A. group sort
B. radix sort
C. bin sort
D. uniform sort
Select an option to see the answer and solution.
What is the worst case time complexity of tree sort (when implemented with a balanced tree)?
A. O(n)
B. O(n log n)
C. O(n2 )
D. O(log n)
Select an option to see the answer and solution.
What is the worst case time complexity of the binary tree sort?
A. O(n)
B. O(nlogn)
C. O(n2 )
D. O(logn)
Select an option to see the answer and solution.
Which of the following sorting algorithms is the fastest?
A. Merge sort
B. Shell sort
C. Insertion sort
D. Quick sort
Select an option to see the answer and solution.
In addition to the pancake sorting problem, there is the case of the burnt pancake problem in which we are dealing with pancakes (discs) that are burnt on one side only. In this case it is taken that the burnt side must always end up . . . . . . . .
A. Faced down
B. Faced up
C. It doesn't matter
D. Both sides are burnt
Select an option to see the answer and solution.
What is the time taken to perform a delete min operation?
A. O(N)
B. O(N log N)
C. O(log N)
D. O(N2 )
Select an option to see the answer and solution.
Which of the following uses the largest amount of auxiliary space for sorting?
A. Bubble sort
B. Counting sort
C. Quick sort
D. Heap sort
Select an option to see the answer and solution.
Which of the following is an in-place sorting algorithm?
A. Merge sort
B. Permutation sort
C. Radix sort
D. Counting sort
Select an option to see the answer and solution.
What is the average case time complexity of standard merge sort?
A. O(n log n)
B. O(n2 )
C. O(n2 log n)
D. O(n log n2 )
Select an option to see the answer and solution.
What is the average case time complexity of binary insertion sort?
A. O(n)
B. O(n log n)
C. O(n2 )
D. O(log n)
Select an option to see the answer and solution.
What is the best case time complexity of comb sort and bubble sort respectively?
A. O(n2 ) and O(n log n)
B. O(n log n) and O(n)
C. O(n) and O(n2 )
D. O(n2 /2a ) (a=number of increment) and O(n2 )
Select an option to see the answer and solution.
Merge sort uses which of the following method to implement sorting?
A. selection
B. exchanging
C. merging
D. partitioning
Select an option to see the answer and solution.
The worst case time complexity of tree sort remains unaffected when implemented with an unbalanced tree or a balanced tree.
Select an option to see the answer and solution.
Library sort is an online sorting algorithm.
Select an option to see the answer and solution.
Sleep sort should be preferred over bogosort as it has better time complexity.
Select an option to see the answer and solution.
