The Gateway to Computer Science Excellence
+1 vote
636 views

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

But how ????
 

in Algorithms by (101 points) | 636 views
+1
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 )$
+1
Yeah,  when the graph is complete then we use adjacency matrix which gives O(v^2)
+1
@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.
+1
@ 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.
0
@Shubham Shukla - The input space is not considered while calculating space complexity.
0
@ hardik

can you show me where it is written.?
0
Both input and extra space taken by the algorithm during its running time is considered during calculating the time complexities

1 Answer

0 votes
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).
by Junior (909 points)
0
It is wrong. It will be O(V).
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
50,737 questions
57,385 answers
198,558 comments
105,371 users