In the following table, the left column contains the names of standard graph algorithms and the right column contains the time complexities of the algorithms. Here, n and m are number of vertices and edges, respectively. Match each algorithm with its time complexity. Choose the correct answer from the options given below :List I List II Standard graph algorithms Time complexities A. Bellman‐Ford algorithm I. O(m*log n) B. Kruskal’s algorithm II. O(n 3) C. Floyd‐Warshall algorithm III. O(n*m) D. Topological sorting IV. O(n + m)
A ‐ III, B ‐ I, C ‐ II, D ‐ IV
This question asks us to match standard graph algorithms with their corresponding time complexities, given the number of vertices (n) and edges (m) in a graph.
Let's analyze each algorithm and its typical time complexity:
Understanding Bellman‐Ford Algorithm Time Complexity
The Bellman‐Ford algorithm is used to find the shortest paths from a single source vertex to all other vertices in a weighted graph. It is particularly useful because it can handle graphs with negative edge weights, provided there are no negative-weight cycles reachable from the source. The algorithm works by relaxing all edges $n-1$ times. For each relaxation pass, it iterates through all $m$ edges. Therefore, the time complexity of the Bellman‐Ford algorithm is $\text{O}(n \times m)$.
This matches Time Complexity III: $\text{O}(n*m)$.
Understanding Kruskal’s Algorithm Time Complexity
Kruskal’s algorithm is a greedy algorithm used to find a Minimum Spanning Tree (MST) for a connected, weighted, undirected graph. It works by sorting all the edges by weight and adding the edge with the lowest weight to the MST if it does not form a cycle. The dominant steps are sorting the edges and using a disjoint-set data structure (Union-Find) to check for cycles. Sorting the $m$ edges takes $\text{O}(m \text{ log } m)$ time. The Union-Find operations for $m$ edges and $n$ vertices take nearly linear time, specifically $\text{O}(m \alpha(n))$, where $\alpha$ is the inverse Ackermann function, which is very slow growing and often considered effectively constant. Thus, the overall time complexity is dominated by the sorting step, which is $\text{O}(m \text{ log } m)$. Since for any graph, $m \le n^2$, we have $\text{log } m \le \text{log } n^2 = 2 \text{ log } n$. Thus, $\text{O}(m \text{ log } m)$ is asymptotically equivalent to $\text{O}(m \text{ log } n)$ when considering sparse graphs where $m$ is closer to $n$, and $\text{O}(m \text{ log } n)$ is given as an option.
This matches Time Complexity I: $\text{O}(m*\text{log } n)$.
Understanding Floyd‐Warshall Algorithm Time Complexity
The Floyd‐Warshall algorithm is an all-pairs shortest path algorithm. It finds the shortest paths between all pairs of vertices in a weighted graph. It is a dynamic programming algorithm that considers all possible intermediate vertices $k$ ($1 \le k \le n$) for paths between any pair of vertices $(i, j)$. The algorithm involves three nested loops, each iterating up to $n$ times. Therefore, the time complexity of the Floyd‐Warshall algorithm is $\text{O}(n^3)$.
This matches Time Complexity II: $\text{O}(n^3)$.
Understanding Topological Sorting Time Complexity
Topological sorting is an ordering of the vertices of a Directed Acyclic Graph (DAG) such that for every directed edge $u \to v$, vertex $u$ comes before vertex $v$ in the ordering. This sorting is only possible for DAGs. Common algorithms for topological sorting are based on Depth First Search (DFS) or Kahn's algorithm (using in-degrees). Both approaches visit each vertex and each edge exactly once. The time complexity for topological sorting is $\text{O}(n + m)$, where $n$ is the number of vertices and $m$ is the number of edges.
This matches Time Complexity IV: $\text{O}(n + m)$.
Matching the Graph Algorithms and Time Complexities
Based on the analysis above, we can create the following mapping:
- Bellman‐Ford algorithm (A) maps to $\text{O}(n*m)$ (III).
- Kruskal’s algorithm (B) maps to $\text{O}(m*\text{log } n)$ (I).
- Floyd‐Warshall algorithm (C) maps to $\text{O}(n^3)$ (II).
- Topological sorting (D) maps to $\text{O}(n + m)$ (IV).
Let's summarize the matching in a table:
| Algorithm | Match | Time Complexity |
|---|---|---|
| A. Bellman‐Ford | III | $\text{O}(n*m)$ |
| B. Kruskal’s | I | $\text{O}(m*\text{log } n)$ |
| C. Floyd‐Warshall | II | $\text{O}(n^3)$ |
| D. Topological sorting | IV | $\text{O}(n + m)$ |
The correct matching is A ‐ III, B ‐ I, C ‐ II, D ‐ IV.
Revision Table: Graph Algorithm Complexities
| Algorithm | Purpose | Time Complexity |
|---|---|---|
| Bellman‐Ford | Single Source Shortest Path (with negative weights) | $\text{O}(n \cdot m)$ |
| Kruskal’s | Minimum Spanning Tree | $\text{O}(m \text{ log } m)$ or $\text{O}(m \text{ log } n)$ |
| Floyd‐Warshall | All Pairs Shortest Path | $\text{O}(n^3)$ |
| Topological sorting | Linear ordering of DAG vertices | $\text{O}(n + m)$ |
Additional Information on Graph Algorithms and Analysis
Understanding the time complexity of graph algorithms is crucial in computer science. The complexity tells us how the runtime of an algorithm scales with the size of the input, represented here by the number of vertices ($n$) and edges ($m$).
- Big O Notation: $\text{O}(\cdot)$ notation describes the upper bound of an algorithm's runtime in terms of the input size. It helps compare algorithms and predict performance for large inputs.
- Graph Types: The efficiency of an algorithm can depend on whether the graph is directed or undirected, weighted or unweighted, and whether it contains cycles.
- Shortest Path Algorithms: Besides Bellman‐Ford and Floyd‐Warshall, Dijkstra's algorithm is another important single-source shortest path algorithm for graphs with non-negative edge weights. Its time complexity using a priority queue is typically $\text{O}(m + n \text{ log } n)$.
- Minimum Spanning Tree Algorithms: Prim's algorithm is another common MST algorithm, which can be implemented efficiently using a priority queue to achieve a time complexity of $\text{O}(m + n \text{ log } n)$.
When analyzing graph algorithms, both the number of vertices and edges are important parameters, especially for sparse graphs (where $m$ is much smaller than $n^2$) versus dense graphs (where $m$ is closer to $n^2$).
Important Questions from Introduction
How many cards must be selected from a standard deck of 52 cards to guarantee that at least three hearts are present among them?
Match List 1 with List 2 and choose the correct answer from the code given below:
List I
(Graph Algorithm)
List II
(Time Complexity)
a) Dijkstra’s algorithm
i) Θ(E log E)
b) Kruskal’s algorithm
ii) Θ(V 3)
c) Floyd-Warshall algorithm
iii) Θ(V 2)
d) Topological sorting
iv) Θ(V + E)
Where V and E are the number of vertices and edges in graph respectively.
The solution of recurrence relation: T(n)=2T(sqrt(n)) + lg(n) is
Modulus of elasticity of concrete, E is calculated using:
In how many types can R.C.C. be classified into?
