closed by
2,454 views
1 votes
1 votes
closed with the note: resolved

Question Source - https://gateoverflow.in/1374/gate2005-38

Let G(V,E)be an undirected graph with positive edge weights. Dijkstra’s single source shortest path algorithm can be implemented using the binary heap data structure with time complexity:

 1. O(|V|2)
 2. O(|E|+|V|log|V|)
 3. O(|V|log|V|)
 4. O((|E|+|V|)log|V|)

========================================================================

Correct answer is -  

> 4. O((|E|+|V|)log|V|)

=========================================================================

My Approach is as follows - 

O(V+V+VlogV+ElogV) = O(ElogV)

 - O(V) to initialize.
 - O(V) to Build Heap.
 - VlogV to perform Extract_Min
 - ElogV to perform Decrease Key

> Now, as I get O(ElogV) and when I see options, a part of me says the
> correct one is O(VlogV) because for a sparse Graph |V| = |E|, but as I
> said the correct answer is O((|E|+|V|)log|V|). So, where am I going
> wrong?

closed by

1 Answer

Best answer
2 votes
2 votes

correct one is O(VlogV) because for a sparse Graph |V| = |E|

Who said it is a Sparse Graph? Question doesn't say that. What if It were a Dense Graph?  

selected by

Related questions

11 votes
11 votes
5 answers
1
Vikrant Singh asked Dec 28, 2014
3,610 views
What is the complexity of finding $50^{th}$ smallest element in an already constructed binary min-heap?$\Theta(1)$$\Theta (\log n)$$\Theta (n)$$\Theta (n \log n)$
9 votes
9 votes
2 answers
4
vineet.ildm asked Nov 7, 2016
5,807 views
Why space complexity of heapsort is O(1)....and why not O(logn)..because of space required by recursion calls which is equivalent to height of the tree...where am i getti...