All Exams Test series for 1 year @ ₹349 only
Question

Arrange the following algorithms from the most efficient to least efficient based on their time complexity. 

A. Kruskal's Algorithm

 B. Breadth first search Algorithm 

C. Bellman-Ford Algorithm

 D. Dijkstra's Algorithm 

E. Edmonds-Karp Algorithm. 

Choose the correct answer from the options given below:

The correct answer is
B, D, A, C, E

The question asks to arrange five graph algorithms based on their time complexity, from the most efficient (lowest time complexity) to the least efficient (highest time complexity).

Algorithm Time Complexities

We need to determine the standard time complexity for each algorithm:

  • B. Breadth-First Search (BFS): Used for traversing graphs. Its time complexity is $O(V + E)$ where $V$ is the number of vertices and $E$ is the number of edges.
  • D. Dijkstra's Algorithm: Finds the shortest paths from a single source vertex in a graph with non-negative edge weights. With a binary heap, its complexity is typically $O(E \log V)$.
  • A. Kruskal's Algorithm: Finds a Minimum Spanning Tree (MST) for a connected, undirected graph. Its time complexity is often stated as $O(E \log E)$ or $O(E \log V)$, depending on the implementation of the disjoint-set data structure and sorting.
  • C. Bellman-Ford Algorithm: Finds the shortest paths from a single source vertex, even with negative edge weights (but no negative cycles). Its time complexity is $O(V \cdot E)$.
  • E. Edmonds-Karp Algorithm: A specific implementation of the Ford-Fulkerson method for finding the maximum flow in a network. Its time complexity is $O(V \cdot E^2)$.

Ordering Algorithms by Efficiency

To order the algorithms from most to least efficient, we compare their time complexities:

  1. Most Efficient: $O(V + E)$ is the lowest complexity. (BFS)
  2. Next Efficient: $O(E \log V)$ (Dijkstra's, Kruskal's) are generally faster than polynomial complexities involving $V$ or $E$. Dijkstra's and Kruskal's have similar complexities in many common scenarios.
  3. Less Efficient: $O(V \cdot E)$ is significantly slower than logarithmic complexities. (Bellman-Ford)
  4. Least Efficient: $O(V \cdot E^2)$ is the highest complexity among these. (Edmonds-Karp)

Based on this analysis, the order from most efficient to least efficient is:

B (BFS, $O(V + E)$) > D (Dijkstra, $O(E \log V)$) > A (Kruskal's, $O(E \log V)$) > C (Bellman-Ford, $O(V \cdot E)$) > E (Edmonds-Karp, $O(V \cdot E^2)$).

Therefore, the correct sequence is B, D, A, C, E.

Was this answer helpful?

Important Questions from Asymptotic Worst Case Time and Time Complexity

  1. Arrange the following in ascending order of their average case complexity.

    Selection-sort, Quick-sort, Linear search, Binary search

  2. What is the average case time complexity of merge sort?
  3. Which of the following is correct order of increasing time complexity of algorithms

     A. Tower of Hanoi with n disk. 

    B. Binary search given n sorted numbers. 

    C. Heap sort given n numbers at the worst case. 

    D. Addition of two n x n matrices. 

    Choose the correct answer from the options given below:

Need Expert Advice?

Start Your Preparation with Prepp Mobile App

Download the app from Google Play & App Store
Download the app from Google Play & App Store
Prepp Mobile App