Question Id : 18795 |
Context : UGC NET Computer Science Sep 2022 (Paper II)
Consider the following algorithms and their running times:
| 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)$ |
Which one of the following is correct?
🎥 Video solution / Text Solution of this question is given below:
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)$
3