1 vote

For a sparse graph $G=(V,E)$ where $|E|=\Theta (V)$ is the implementation of Prim’s algorithm with a Fibonacci heap asymptotically faster than the binary-heap implementation? What about for a dense graph, where $|E|=\Theta (V)^{2}$? How must the sizes $|E|$ and $|V|$ be related for the Fibonacci-heap implementation to be asymptotically faster than the binary-heap implementation?

__________________________________________________________________________

Plz tell me difference between Sparse and Dense graph here? How Dense graph implemented and how it make difference for this question

__________________________________________________________________________

Plz tell me difference between Sparse and Dense graph here? How Dense graph implemented and how it make difference for this question

0

the first link you provided for

difference btw array implementation and heap implementation

but your question contains Fibonacci heap and binary heap.

i got one doubt in that same question, Arjun sir mentioned that (V^{2} . log V) is asymptotically equal, how they are equal?

0

Time complexity of prims algorithm when binary heap is used is $O(ElogV)$

Time complexity of prims algorithm when fibonacci heap is used is $O(E + VlogV)$

Now, for a sparse graph(where the number of edges are of the order of number of vertices i.e. $E=\theta(V)$, then time complexity becomes

$O(VlogV)$ for binary heap and

$O(V + VlogV)=O(VlogV)$ for fibonacci heap

For a dense graph (where edges might exist in every two vertices i.e. near to $\frac{V(V-1)}{2}$ which is $O(V^2)$ i.e. $E=O(V^2)$), the time complexity becomes,

$O(V^2logV)$ for binary heap and

$O(V^2+VlogV) = O(V^2)$ for fibonacci heap.

Time complexity of prims algorithm when fibonacci heap is used is $O(E + VlogV)$

Now, for a sparse graph(where the number of edges are of the order of number of vertices i.e. $E=\theta(V)$, then time complexity becomes

$O(VlogV)$ for binary heap and

$O(V + VlogV)=O(VlogV)$ for fibonacci heap

For a dense graph (where edges might exist in every two vertices i.e. near to $\frac{V(V-1)}{2}$ which is $O(V^2)$ i.e. $E=O(V^2)$), the time complexity becomes,

$O(V^2logV)$ for binary heap and

$O(V^2+VlogV) = O(V^2)$ for fibonacci heap.