in Algorithms
2,641 views
1 vote
1 vote

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

But how ????
 

in Algorithms
2.6k views

4 Comments

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

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

1 Answer

0 votes
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).

1 comment

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

Related questions