Space Complexity of Dijkastra's algorithm

Question

I read that the space complexity of Dijasktra is $O(V^2)$ . (http://igraph.wikidot.com/algorithm-space-time-complexity)

But how ????
 

Comments

In worst case, it is a complete graph and have to visit every edge

So, space complexity will be $\binom{v}{2}=\frac{v(v-1)}{2}=\theta \left ( v^{2}\right )$

---

Yeah,  when the graph is complete then we use adjacency matrix which gives O(v^2)

---

@amitpandey675 - No, the adjacency matrix is given as an input to the algorithm, so it would not be considered in the calculation of space complexity.

---

@ hardik NO

when you calculate space complexity you add both input and extra space in total taken...here Space complexity=input space+extra space= O(V^2)+O(1)=O(V^2).

why O(V^2) in above comments its explained.

---

@Shubham Shukla - The input space is not considered while calculating space complexity.

---

@ hardik

can you show me where it is written.?

---

Both input and extra space taken by the algorithm during its running time is considered during calculating the time complexities

Answer 1

In the worst case scenario,i.e. in a complete graph, no. of edges become v(v-1)/2 i.e e~v^2.

Now,even with adjacency list implementation,which takes O(V + E),as E~V^2 , O(V+E)~O(V^2).

Comments

It is wrong. It will be O(V).