+1 vote
250 views

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|)

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

> 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 with the note: resolved
closed | 250 views

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
+1
Yes, you're right and that's what I realized now. Thank you, Deepak Bhai ! :)
0
Always brother :)

1
2