Question

Consider the following statements given below:

$S_1$: Consider a unweighted undirected connected graph G[V, E] worst case time complexity to check it two particular vertices U, V present in the graph is O (V + E). Check it two particular vertices U, V present in the graph is O (V + E).

$S_2$: Dijkstra's algorithm may produce incorrect result if it contain negative weight cycle.

$S_3$: The worst case running time complexity to search for an element in a balanced binary search tree with n element is O(n).

Which of the above statement is correct?

• A. $Only{S}_{1}and{S}_2$
• B. $Only{S}_2$
• C. $Only{S}_{2}and{S}_3$
• D. $Only{S}_{1}and{S}_3$

Answer 1

The correct option is A $Only{S}_{1}and{S}_2$

(d)

$S_1$ For checking two particular vertices present in graph or not. BFS can be used it take O(V+E).

$S_{1}iscorrect$

$S_2$ Negative weight cycle contain cycle whose weight is negative. Dijkstra's algorithm may produce incorrect result if it contain negative weight cycle.

$S_{2}iscorrect$