Aspire's Library
A Place for Latest Exam wise Questions, Videos, Previous Year Papers,
Study Stuff for MCA Examinations - NIMCET
Study Stuff for MCA Examinations - NIMCET
Previous Year Question (PYQs)
Consider the following algorithms and their running times:
Which one of the following is correct?
| List I | List II |
|---|---|
| (A) Breadth First Search | (I) $\theta(V+E)$ |
| (B) Rabin-Karp Algorithm | (II) $O(V+E)$ |
| (C) Depth-First Search | (III) $\theta((n-m+1)m)$ |
| (D) Heap sort (worst case) | (IV) $O(n^2)$ |
| (E) Quick sort (worst case) | (V) $O(n\log n)$ |
Solution
Breadth First Search visits every vertex and every edge of a graph.So, its time complexity is:
$O(V+E)$
Therefore,
$(A)-(II)$
Rabin-Karp Algorithm compares the pattern of length $m$ with possible positions in the text.
In the worst case, it may take:
$\theta((n-m+1)m)$
Therefore,
$(B)-(III)$
Depth-First Search also visits every vertex and every edge.
So, its running time is:
$\theta(V+E)$
Therefore,
$(C)-(I)$
Heap sort has worst case time complexity:
$O(n\log n)$
Therefore,
$(D)-(V)$
Quick sort has worst case time complexity:
$O(n^2)$
This happens when partitioning is highly unbalanced.
Therefore,
$(E)-(IV)$
Final matching is:
$(A)-(II), (B)-(III), (C)-(I), (D)-(V), (E)-(IV)$
Online Test Series, Information About Examination,
Syllabus, Notification
and More.
View More
Online Test Series, Information About Examination,
Syllabus, Notification
and More.
View More
Ask Your Question or Put Your Review.
