Follow Us :

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:

  • Option : D
  • Explanation :
    Worst Case
    Insertion sort → O(n2
    Merge sort → O(n log n)
    Quick sort → O(n2)
Cancel reply

Your email address will not be published. Required fields are marked *


Cancel reply

Your email address will not be published. Required fields are marked *


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 Θ(n2) time
II. Bubblesort runs in Θ(n2) time
III. Mergesort runs in Θ(n) time
IV. Insertion sort runs in Θ(n) time

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

Your email address will not be published. Required fields are marked *


Cancel reply

Your email address will not be published. Required fields are marked *


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-IList-II
1.Bellman-Ford algorithmA.O(mlog n)
2.Kruskal's algorithmB.O(n3)
3.Floyd-Warshall algorithmC.O(nm)
4.Topological sortingD.O(n + m)

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

Your email address will not be published. Required fields are marked *


Cancel reply

Your email address will not be published. Required fields are marked *


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

  • 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
Cancel reply

Your email address will not be published. Required fields are marked *


Cancel reply

Your email address will not be published. Required fields are marked *


90. Consider n jobs J1, J2,..., Jn such that job Ji has execution time ti and a non-negative integer weight wi. The weighted mean completion time of the jobs is defined to be

where Ti is the completion time of job Ji. 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?

  • Option : D
  • Explanation :
    Non-increasing order of wi/ti
Cancel reply

Your email address will not be published. Required fields are marked *


Cancel reply

Your email address will not be published. Required fields are marked *


Related Quiz.
Performance Analysis of Algorithms and Recurrences