The Gateway to Computer Science Excellence

+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.

- All categories
- General Aptitude 1.9k
- Engineering Mathematics 7.5k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.4k
- Theory of Computation 6.2k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.2k
- Non GATE 1.4k
- Others 1.4k
- Admissions 595
- Exam Queries 573
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 18

50,737 questions

57,292 answers

198,229 comments

104,909 users