Question

Consider a greedy algorithm that solves the problem of finding a minimum spanning tree of a graph. Which one of the following best describes the asymptotical running time?

a) O(m + n)
b) O(n log m)
c) O(m log n)
d) O(mn)

Answer 1

The asymptotical running time of a greedy algorithm for finding a minimum spanning tree of a graph is O(m log n).

Step-by-step explanation:

The asymptotical running time of a greedy algorithm for finding a minimum spanning tree of a graph can be described as O(m log n). The 'm' represents the number of edges in the graph, and 'n' represents the number of vertices. The running time is dependent on the number of edges and vertices.

Greedy algorithms have a time complexity of O(E log V), where 'E' is the number of edges and 'V' is the number of vertices in the graph. In the case of finding a minimum spanning tree, 'E' is the same as 'm' and 'V' is the same as 'n'. Therefore, the asymptotical running time is O(m log n).

For example, if a graph has 10 vertices and 20 edges, the running time of the greedy algorithm would be in the order of 20 log 10 = 20 * 3 = 60 units of time