The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

0 votes

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

+1 vote

Best answer

- All categories
- General Aptitude 1.6k
- Engineering Mathematics 7.3k
- Digital Logic 2.7k
- Programming & DS 4.9k
- Algorithms 4.2k
- Theory of Computation 5.4k
- Compiler Design 2.1k
- Databases 4k
- CO & Architecture 3.5k
- Computer Networks 4.2k
- Non GATE 1.4k
- Others 1.5k
- Admissions 570
- Exam Queries 566
- Tier 1 Placement Questions 23
- Job Queries 70
- Projects 18

48,756 questions

52,850 answers

183,548 comments

68,744 users