Data Structures and Algorithms MCQ - Performance Analysis of Algorithms and Recurrences

86 The worst case running times of Insertion sort, Merge sort and Quick sort, respectively, are:

Worst Case
Insertion sort → O(n²
Merge sort → O(n log n)
Quick sort → O(n²)

87 Assume that the algorithms considered here sort the input sequences in ascending order. If the input is already in the ascending order, which of the following are TRUE?
I. Quicksort runs in Θ(n²) time
II. Bubblesort runs in Θ(n²) time
III. Mergesort runs in Θ(n) time
IV. Insertion sort runs in Θ(n) time

1. Quicksort will take worst case, if the input is in ascending order i.e Θ(n²)
2. Insertion sort runs in Θ(n) time.

88 In the following table, the left column contains the names of standard graph algorithms and the right column contains the time complexities of the algorithms. Match each algorithm with its time complexity.

List-I		List-II
1.	Bellman-Ford algorithm	A.	O(mlog n)
2.	Kruskal's algorithm	B.	O(n³)
3.	Floyd-Warshall algorithm	C.	O(nm)
4.	Topological sorting	D.	O(n + m)

Bellman ford = O(n*m)
Kruskal’s Alqo = O(m logn)
Floyd war shall = O(n³)
Topological sort = O(n+m)

89 In an unweighted, undirected connected graph, the shortest path from a node S to every other node is computed most efficiently, in terms of time complexity, by

In case of unweighted, undirected graphs, BFS gives the most time efficient computation for shortest path. It is guaranteed to find first shortest path

90 Consider n jobs J₁, J₂,..., J_n such that job J_i has execution time t_i and a non-negative integer weight w_i. The weighted mean completion time of the jobs is defined to be

where T_i is the completion time of job J_i. Assuming that there is only one processor available, in what order must the jobs be executed in order to minimize the weighted mean completion time of the jobs?

Non-increasing order of w_i/t_i