Register

GO Classes Test Series | Data Structures and Algorithms | Basic graph algorithms: traversals and Shortest path | Question: 1

• edited by
452 views
2 2 votes

Consider the given two statements.

  • $\mathrm{S} 1:$ Depth-first search is asymptotically faster than breadth-first search.
  • $\mathrm{S} 2:$ Deleting an element from a binary search tree takes $\mathrm{O}(\mathrm{lg} n)$ time in the worst case.

Which of the following is correct about $\mathrm{S} 1$ and $\mathrm{S} 2?$

  1. $\mathrm{S} 1$ is correct but $\mathrm{S} 2$ is wrong.
  2. $\mathrm{S} 2$ is correct but $\mathrm{S} 1$ is wrong.
  3. Both are correct
  4. Both are False

1 Answer

2 2 votes
$\mathrm{S} 1$ is False. They both take $O\text{(V + E)}$ time.
$\mathrm{S} 2$ is False. It takes $O(h)$ time and for an ordinary binary search tree, $h$ can be $\omega(\lg n)$.
Voting & Accepting an answer helps improve the community
Answer:
← Previous · GO Classes Test Seri...Next → · probability
← Previous in category · GO Classes Test Seri...Next in category → · ISI2022 - MCS - PCB ...
Position:
Show:

Related questions

3 3 votes
3 3 answers
671
671 views
GO Classes asked Oct 16, 2024
671 views
GO Classes Test Series | Data Structures and Algorithms | Basic graph algorithms: traversals and Shortest path | Question: 2
Consider the given graph $\text{G}.$ Traversal trees $\text{T1}$ and $\text{T2}$ (given below) are made by DFS or BFS traversals starting from s..Which of the following i...
0 0 votes
1 1 answer
213
213 views
GO Classes asked Oct 16, 2024
213 views
GO Classes Test Series | Data Structures and Algorithms | Basic graph algorithms: traversals and Shortest path | Question: 5
Consider performing a depth-first search (DFS) on an undirected and unweighted graph $G$ starting at vertex $s$. For any vertex $u$ in $G, d[u]$ is the length of the shor...
0 0 votes
2 2 answers
253
253 views
GO Classes asked Oct 16, 2024
253 views
GO Classes Test Series | Data Structures and Algorithms | Basic graph algorithms: traversals and Shortest path | Question: 6
Which of the following is/are TRUE ?If we perform DFS on an undirected graph, there are no cross edges.If the DFS tree has no back edges, then there are no cycles in the ...
1 1 vote
1 1 answer
329
329 views
GO Classes asked Oct 16, 2024
329 views
GO Classes Test Series | Data Structures and Algorithms | Basic graph algorithms: traversals and Shortest path | Question: 7
Which of the following is correct option about $\mathrm{S} 1$ and $\mathrm{S} 2?$$\mathrm{S} 1:$ If $\text{G}$ is a weighted graph with $n$ vertices and $m$ edges that do...