443 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

2 Answers

1 votes
1 votes
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)
Answer:

Related questions

2 votes
2 votes
2 answers
2
Bikram asked Oct 4, 2016
346 views
$$T(n) = \begin{cases} 4 & \quad if \: \: n =1 \\ T(n-1) + 4 & \quad otherwise \end{cases}$$Value of $T(1000)$ is ___
3 votes
3 votes
1 answer
4
Bikram asked Oct 4, 2016
501 views
Maximum element in a min-heap represented by an array, can be computed in _____ time$O(n)$$O(\log n)$$O(n \log n)$ but not $O(n)$$O(1)$