edited by
1,825 views
0 votes
0 votes

The time complexities of some standard graph algorithms are given. Match each algorithm with its time complexity ? ($n$ and $m$ are no. of nodes and edges respectively)

$\begin{array}{clcl}  \text{a.} & \text{Bellman Ford algorithm} & \text{i.} & O(m\log n)  \\ \text{b.} & \text{Kruskals algorithm} & \text{ii.} & O(n^3) \\  \text{c.} & \text{Floyd Warshall algorithm } & \text{iii.} & O(mn) \\ \text{d.} & \text{Topological sorting} & \text{iv.} & O(n+m) \\ \end{array}$

$\textbf{Codes :}$

  1. $\text{a-iii, b-i, c-ii, d-iv}$
  2. $\text{a-ii, b-iv, c-iii, d-i}$
  3. $\text{a-iii, b-iv, c-i, d-ii}$
  4. $\text{a-ii, b-i, c-iii, d-iv}$
edited by

1 Answer

1 votes
1 votes

Ans. Option A.
Time complexities:
(a) Bellman Ford algorithm - O(mn)
(b) Kruskals algorithm - O(mlogn)
(c) Floyd Wrashall algorithm - O(n3)
(d) Topological sort - O(n + m)
where n and m are no. of nodes and edges respectively.

Reference: CLRS book.

Answer:

Related questions

2 votes
2 votes
2 answers
1
1 votes
1 votes
3 answers
2
go_editor asked Jul 12, 2016
1,246 views
Let $T(n)$ be a function defined by $T(n) =1$ and $T(n)=2T (n/2) + \sqrt{n}$, which of the following is true?$T(n) = O(\sqrt{n})$$T(n) = O(\log_2 n)$$T(n) = O(n)$$T(n) = ...
1 votes
1 votes
1 answer
4
go_editor asked Jul 13, 2016
3,032 views
A* algorithm is guaranteed to find an optimal solution ifh’ is always 0g is always 1h’ never overestimates hh’ never underestimates h