Data Structures and Algorithms - Performance Analysis of Algorithms and Recurrences

Avatto > > UGC NET COMPUTER SCIENCE > > PRACTICE QUESTIONS > > Data Structures and Algorithms > > Performance Analysis of Algorithms and Recurrences

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

Answer
Comment
Array

Option : D
Explanation :
Worst Case
Insertion sort → O(n²
Merge sort → O(n log n)
Quick sort → O(n²)

You must be logged in to post a comment.

You must be logged in to post a comment.

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

Answer
Comment
Array

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

You must be logged in to post a comment.

You must be logged in to post a comment.

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)

Answer
Comment
Array

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

You must be logged in to post a comment.

You must be logged in to post a comment.

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

Answer
Comment
Array

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

You must be logged in to post a comment.

You must be logged in to post a comment.

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?

Answer
Comment
Array

Option : D
Explanation :
Non-increasing order of w_i/t_i

You must be logged in to post a comment.

You must be logged in to post a comment.

Related Quiz.
Performance Analysis of Algorithms and Recurrences

Forgot your password?

I agree with the Terms.