The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+1 vote

Question Source -

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 (7.9k points)
closed by | 250 views

1 Answer

+2 votes
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 (25k points)
selected by
Yes, you're right and that's what I realized now. Thank you, Deepak Bhai ! :)
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
49,783 questions
54,511 answers
75,111 users