The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
0 votes
202 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|)

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

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 with the note: resolved
asked in Algorithms by Loyal (9.6k points)
closed by | 202 views

1 Answer

+1 vote
Best answer

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?  

answered by Boss (23.4k points)
selected by
+1
Yes, you're right and that's what I realized now. Thank you, Deepak Bhai ! :)
0
Always brother :)

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
48,756 questions
52,850 answers
183,548 comments
68,744 users