in Algorithms
192 views
2 votes
2 votes

Match the following:
 

i.

BFS

a. $O(\mid E \mid + \mid V \mid \log \mid V \mid)$
ii. DFS b. $O(E)$
iii. Kruskal's algorithm c. Stack
iv. Dijikstra's Algorithm d. $O(E \log V)$
  1. i - b, ii - c, iii - a, iv - d
  2. i - c, ii - b, iii - d, iv - a
  3. i - b, ii - c, iii - d, iv - a
  4. i - c, ii - d, iii - a, iv - b
in Algorithms
by
192 views

2 Answers

2 votes
2 votes
c is correct answer
reshown by
1 vote
1 vote
When use fibanocci heap dijkstra take O(E+VlogV). Kruskal always takes O(ElogE+VlogV) ..  Ei s O(V^2) so T=O(2ElogV+VlogV) or

O( ElogV)(assuming graph is not a sparse graph)

DFS is implemented using  stack

BFS O(E+V) =O(E) (again assuming graph is a dense graph)

3 Comments

Kruskal's and Dijikstra have same TC. if you can implement Dijikstr'as algo with FIbnocci heap then kruskal's can also be done.
this paper is really strange!!
0
0
Kruskal can take O(∣E∣+∣V∣log∣V∣) , if sorting of edges is done in preprocessing step.

And Dijkstra can take O(ElogV) , by min heap.

so A) is also possible.
0
0
Kruskal can be done in O(∣E∣+∣V∣log∣V∣) , edges are sorted in pre processing step.

Dijkstra can be implemented in O(ElogV) by min heap .

 So A) is also possible.
0
0
Answer:

Related questions