Register

GO Classes 2024 | IIITH Mock Test 5 | Question: 23

• retagged by
346 views
2 votes
2 votes
Which of the following is/are TRUE?
  1. In the worst case, merge sort runs in $O\left(n^2\right)$ time.
  2. Depth-first search of a graph is asymptotically faster than breadth-first search.
  3. Dijkstra's algorithm is an example of a greedy algorithm.
  4. Insertion in a binary search tree is $\text{“commutative"}.$ That is, inserting $x$ and then $y$ into a binary search tree leaves the same tree as inserting $y$ and then $x$.
• retagged by
User Avatar

1 Answer

1 votes
1 votes
  1. True. Merge sort runs in $O(n \lg n)$ time which is $O\left(n^2\right)$.

  2. False. They both run in time $\Theta(\text{V + E})$.

  3. True.

  4. False. Consider inserting $x, y$ in an empty binary search tree to see why.
User Avatar
Voting & Accepting an answer helps improve the community
Answer:
← PreviousNext →
← Previous in categoryNext in category →

Related questions

303
views
1 answers
2 votes
GO Classes asked Apr 30, 2023
303 views
GO Classes 2024 | IIITH Mock Test 5 | Question: 31
Suppose we have a set of $n$ values. There are always at least one negative value and at least one positive value in the set.What is the worst case time ... known) and arranged in descending order then it takes $\theta(n)$ in worst case.
User Avatar
256
views
1 answers
1 votes
GO Classes asked Apr 30, 2023
256 views
GO Classes 2024 | IIITH Mock Test 5 | Question: 32
Let $\text{G = (V, E)}$ be a simple undirected graph, and $s$ be a particular vertex in it called the source. For $x \in \text{V},$ let $d(x)$ denote the shortest distance in ... $(u, v)$, we have $d[v]=d[u]+1$
User Avatar
Link Copied!