Sorting
Question 1 
The worst case running times of Insertion sort, Merge sort and Quick sort, respectively, are:
Θ(nlogn), Θ(nlogn), and Θ(n^{2})  
Θ(n^{2} ), Θ(n^{2} ), and Θ(nlogn)  
Θ(n^{2}), Θ(nlogn), and Θ(nlogn)  
Θ(n^{2}), Θ(nlogn), and Θ(n^{2}) 
Question 1 Explanation:
Question 2 
Assume that the algorithms considered here sort the input sequences in ascending order. If the input is already in ascending order, which of the following are TRUE?

I. Quicksort runs in Θ(n^{2}) time
II. Bubblesort runs in Θ(n^{2}) time
III. Mergesort runs in Θ(n) time
IV. Insertion sort runs in Θ(n) time
I and II only  
I and III only  
II and IV only  
I and IV only 
Question 2 Explanation:
If input sequence is already sorted then the time complexity of Quick sort will take O(n^{2}) and Bubble sort will take O(n) and Merge sort will takes O(nlogn) and insertion sort will takes O(n).
→ The recurrence relation for Quicksort, if elements are already sorted,
T(n) = T(n1)+O(n) with the help of substitution method it will take O(n^{2}).
→ The recurrence relation for Merge sort, is elements are already sorted,
T(n) = 2T(n/2) + O(n) with the help of substitution method it will take O(nlogn).
We can also use master's theorem [a=2, b=2, k=1, p=0] for above recurrence.
→ The recurrence relation for Quicksort, if elements are already sorted,
T(n) = T(n1)+O(n) with the help of substitution method it will take O(n^{2}).
→ The recurrence relation for Merge sort, is elements are already sorted,
T(n) = 2T(n/2) + O(n) with the help of substitution method it will take O(nlogn).
We can also use master's theorem [a=2, b=2, k=1, p=0] for above recurrence.
Question 3 
You have an array of n elements. Suppose you implement quicksort by always choosing the central element of the array as the pivot. Then the tightest upper bound for the worst case performance is
O(n^{2})  
O(n log n)  
Θ(n logn)  
O(n^{3}) 
Question 3 Explanation:
The Worst case time complexity of quick sort is O (n^{2}). This will happen when the elements of the input array are already in order (ascending or descending), irrespective of position of pivot element in array.
Question 4 
Which one of the following is the tightest upper bound that represents the number of swaps required to sort n numbers using selection sort?
O(log n)  
O(n)  
O(n log n)  
O(n^{2}) 
Question 4 Explanation:
Best, Average and worst case will take maximum O(n) swaps.
Selection sort time complexity O(n^{2}) in terms of number of comparisons. Each of these scans requires one swap for n1 elements (the final element is already in place).
Selection sort time complexity O(n^{2}) in terms of number of comparisons. Each of these scans requires one swap for n1 elements (the final element is already in place).
Question 5 
Which one of the following is the tightest upper bound that represents the time complexity of inserting an object into a binary search tree of n nodes?
O(1)  
O(log n)  
O(n)  
O(n log n) 
Question 5 Explanation:
For skewed binary search tree on n nodes, the tightest upper bound to insert a node is O(n).
Question 6 
What is the time complexity of BellmanFord singlesource shortest path algorithm on a complete graph of n vertices?
Θ(n^{2})  
Θ(n^{2} log n)  
Θ(n^{3})  
Θ(n^{3} log n) 
Question 6 Explanation:
The Bellman–Ford algorithm is an algorithm that computes shortest paths from a single source vertex to all of the other vertices in a weighted digraph. It is capable of handling graphs in which some of the edge weights are negative numbers.
Bellman–Ford runs in O(V * E) time, where V and E are the number of vertices and edges respectively.
Note: For complete graph: E = n(n1)/2 = O(n^{2})
Bellman–Ford runs in O(V * E) time, where V and E are the number of vertices and edges respectively.
Note: For complete graph: E = n(n1)/2 = O(n^{2})
Question 7 
The number of elements that can be sorted in Θ(log n) time using heap sort is
Θ(1)  
Θ(√logn)  
Θ (logn/loglogn)  
Θ(log n) 
Question 7 Explanation:
Using heap sort to n elements it will take O(n log n) time. Assume there are log n/ log log n elements in the heap.
So, Θ((logn/ log log n)log(logn/log log n))
= Θ(logn/log logn (log logn  log log logn))
= Θ((log n/log logn) × log log n)
= Θ (log n)
Hence, option (C) is correct answer.
So, Θ((logn/ log log n)log(logn/log log n))
= Θ(logn/log logn (log logn  log log logn))
= Θ((log n/log logn) × log log n)
= Θ (log n)
Hence, option (C) is correct answer.
Question 8 
What is the number of swaps required to sort n elements using selection sort, in the worst case?
θ(n)
 
θ(n log n)
 
θ(n^{2})  
θ(n^{2} logn)

Question 8 Explanation:
Selection sort – There is no Worst case input for selection sort. Since it searches for the index of kth minimum element in kth iteration and then in one swap, it places that element into its correct position. For n1 iterations of selection sort, it can have O(n) swaps. Selection Sort does a significant number of comparisons before moving each element directly to its final intended position. At most the algorithm requires N swaps. once we swap an element into place, you never go back again.So it is great for writes O(n) but not so great (at all) for reads — O(n^{2}). It isn’t wellsuited to generalized sorting, but might work well in specialized situations like EEPROM (where writes are inordinately expensive).
Question 9 
In quick sort, for sorting n elements, the (n/4)^{th} smallest element is selected as pivot using an O(n) time algorithm. What is the worst case time complexity of the quick sort?
θ(n)
 
θ(n log n)
 
θ(n^{2})
 
θ(n^{2} log n ) 
Question 9 Explanation:
n→n/(4/3)→n/(4/3)^{2}→n/(4/3)^{3}n/(4/3)^{k}=1
n/(4/3)^{k}=1
⇒n=(4/3)^{k}⇒k=log_{4/3}n [k=no. of levels]
In each level workdone = Cn
So, total workdone = Cn⋅log_{4/3}n=(nlog_{4/3}n)
Question 10 
Consider the Quicksort algorithm. Suppose there is a procedure for finding a pivot element which splits the list into two sublists each of which contains at least onefifth of the elements. Let T(n) be the number of comparisons required to sort n elements. Then
T(n) ≤ 2T(n/5) + n
 
T(n) ≤ T(n/5) + T(4n/5) + n
 
T(n) ≤ 2T(4n/5) + n  
T(n) ≤ 2T(n/2) + n

Question 10 Explanation:
Consider the case where one subset of set of n elements contains n/5 elements and another subset of set contains 4n/5 elements.
So, T(n/5) comparisons are needed for the first subset and T(4n/5) comparisons needed for second subset.
Now, suppose that one subset contains more than n/5 elements then another subset will contain less than 4n/5 elements. Due to which time complexity will be less than
T(n/5) + T(4n/5) + n
Because recursion tree will be more balanced.
So, T(n/5) comparisons are needed for the first subset and T(4n/5) comparisons needed for second subset.
Now, suppose that one subset contains more than n/5 elements then another subset will contain less than 4n/5 elements. Due to which time complexity will be less than
T(n/5) + T(4n/5) + n
Because recursion tree will be more balanced.
Question 11 
If we use Radix Sort to sort n integers in the range [n^{k/2}, n^{k}], for some k>0 which is independent of n, the time taken would be?
Θ(n)  
Θ(kn)  
Θ(nlogn)  
Θ(n^{2}) 
Question 11 Explanation:
Question 12 
Which one of the following in place sorting algorithms needs the minimum number of swaps?
Quick sort  
Insertion sort  
Selection sort
 
Heap sort 
Question 12 Explanation:
Selection sort requires minimum number of swaps i.e O(n). The algorithm finds the minimum value, swaps it with the value in the first position, and repeats these steps for the remainder of the list. It does no more than n swaps, and thus is useful where swapping is very expensive.
Question 13 
Let a and b be two sorted arrays containing n integers each, in nondecreasing order. Let c be a sorted array containing 2n integers obtained by merging the two arrays a and b. Assuming the arrays are indexed starting from 0, consider the following four statements
 a[i] ≥ b [i] => c[2i] ≥ a [i]
 a[i] ≥ b [i] => c[2i] ≥ b [i]
 a[i] ≥ b [i] => c[2i] ≤ a [i]
 a[i] ≥ b [i] => c[2i] ≤ b [i]
only I and II  
only I and IV  
only II and III  
only III and IV 
Question 13 Explanation:
a[i] ≥ b[i]
Since both 'a' and 'b' are sorted in the beginning, there are 'i' elements than or equal to a[i] and similarly 'i' elements smaller than or equal to b[i]. So, a[i] ≥ b[i] means there are 2i elements smaller than or equal to a[i] and hence in the merged array, a[i] will come after these 2i elements. So, c[2i] ≤ a[i].
Similarly, a[i] ≥ b[i] says for b that, there are not more than 2i elements smaller than b[i] in the sorted array. So, b[i] ≤ c[2i].
So, option (C) is correct.
Since both 'a' and 'b' are sorted in the beginning, there are 'i' elements than or equal to a[i] and similarly 'i' elements smaller than or equal to b[i]. So, a[i] ≥ b[i] means there are 2i elements smaller than or equal to a[i] and hence in the merged array, a[i] will come after these 2i elements. So, c[2i] ≤ a[i].
Similarly, a[i] ≥ b[i] says for b that, there are not more than 2i elements smaller than b[i] in the sorted array. So, b[i] ≤ c[2i].
So, option (C) is correct.
Question 14 
Let A be a sequence of 8 distinct integers sorted in ascending order. How many distinct pairs of sequences, B and C are there such that (i) each is sorted in ascending order, (ii) B has 5 and C has 3 elements, and (iii) the result of merging B and C gives A?
2  
30  
56  
256 
Question 14 Explanation:
A can have sequence of 8 distinct integers which are sorted in ascending order.
→ If we are pick 3 elements from 8 sequence integers then remaining 5 elements are already in ascending order. After merging these elements then it gives A.
→ No. of possibilities of choosing 8 elements from total of 8 = ^{8}C_{3}
= 8!/3!5!
= 8 * 7
= 56
→ If we are pick 3 elements from 8 sequence integers then remaining 5 elements are already in ascending order. After merging these elements then it gives A.
→ No. of possibilities of choosing 8 elements from total of 8 = ^{8}C_{3}
= 8!/3!5!
= 8 * 7
= 56
Question 15 
In a permutation a1.....an of n distinct integers, an inversion is a pair (ai, aj) such that i < j and ai > aj. If all permutations are equally likely, what is the expected number of inversions in a randomly chosen permutation of 1.....n ?
Question 15 Explanation:
Probability of inverse (a_{i}, a_{j}(i
Probability of expected no. of inversions = (1/2) × (n(n1)/2) = n(n1)/4
Question 16 
In a permutation a1.....an of n distinct integers, an inversion is a pair (ai, aj) such that i < j and ai > aj. What would be the worst case time complexity of the Insertion Sort algorithm, if the inputs are restricted to permutations of 1.....n with at most n inversions?
Θ(n^{2})  
Θ(n log n)
 
Θ(n^{1.5})  
Θ(n) 
Question 16 Explanation:
Here the inputs are to be restricted to 1...n with atmost 'n' inversions. Then the worst case time complexity of inversion sort reduces to Θ(n).
Question 17 
Let s be a sorted array of n integers. Let t(n) denote the time taken for the most efficient algorithm to determined if there are two elements with sum less than 1000 in s. Which of the following statements is true?
t(n) is O(1)  
n ≤ t(n) ≤ n log_{2} n  
Question 17 Explanation:
Since the array is sorted. Now just pick the first two minimum elements and check if their sum is less than 1000 or not. If it is less than 1000 then we found it and if not then it is not possible to get the two elements whose sum is less than 1000. Hence, it takes constant time. So, correct option is (A).
Question 18 
A sorting technique is called stable if
it takes O (nlog n) time  
it maintains the relative order of occurrence of nondistinct elements  
it uses divide and conquer paradigm  
it takes O(n) space 
Question 18 Explanation:
Sorting techniques are said to be stable if it maintains the relative order of occurence of nondistinct element.
Question 19 
8, 9, 15, 20, 47, 4, 12, 17, 30, 40  
8, 15, 20, 47, 4, 9, 30, 40, 12, 17  
15, 20, 47, 4, 8, 9, 12, 30, 40, 17  
4, 8, 9, 15, 20, 47, 12, 17, 30, 40 
Question 19 Explanation:
Question 20 
Merge sort uses
Divide and conquer strategy  
Backtracking approach  
Heuristic search  
Heuristic search 
Question 20 Explanation:
Merge sort uses the divide and conquer strategy.
Question 21 
For merging two sorted lists of sizes m and n into a sorted list of size m+n, we required comparisons of
O(m)  
O(n)  
O(m+n)  
O(logm+logn) 
Question 21 Explanation:
In best case, no. of comparisons is Min(m,n).
In worst case, no. of comparisons is m+n1.
Then we require O(m+n) comparisons to merging two sorted lists.
In worst case, no. of comparisons is m+n1.
Then we require O(m+n) comparisons to merging two sorted lists.
Question 22 
Following algorithm(s) can be used to sort n integers in the range [1...n^{3}] in O(n) time
Heapsort  
Quicksort  
Mergesort  
Radixsort 
Question 22 Explanation:
As no comparison based sort can ever do any better than nlogn. So option (A), (B), (C) are eliminated. O(nlogn) is lower bound for comparison based sorting.
As Radix sort is not comparison based sort (it is counting sort), so can be done in linear time.
As Radix sort is not comparison based sort (it is counting sort), so can be done in linear time.
Question 23 
Randomized quicksort is an extension of quicksort where the pivot is chosen randomly. What is the worst case complexity of sorting n numbers using randomized quicksort?
O(n)  
O(n log n)  
O(n^{2})  
O(n!) 
Question 23 Explanation:
In worst case Randomized quicksort execution time complexity is same as quicksort.
Question 24 
The minimum number of comparisons required to sort 5 elements is _____
7 
Question 24 Explanation:
Minimum no. of comparisons
= ⌈log(n!)⌉
= ⌈log(5!)⌉
= ⌈log(120)⌉
= 7
= ⌈log(n!)⌉
= ⌈log(5!)⌉
= ⌈log(120)⌉
= 7
Question 25 
Quicksort is ________ efficient than heapsort in the worst case.
LESS. 
Question 25 Explanation:
As worst case time for quicksort is O(n^{2}) and worst case for heap sort is O(n logn).
Question 26 
Let P be a quicksort program to sort numbers in ascending order. Let t_{1} and t_{2} be the time taken by the program for the inputs [1 2 3 4] and [5 4 3 2 1] respectively. Which of the following holds?
t_{1} = t_{2}  
t_{1} > t_{2}  
t_{1} < t_{2}  
t_{1} = t_{2} + 5 log 5 
Question 26 Explanation:
Since both are in sorted order and no. of elements in second list is greater.
There are 26 questions to complete.