2 votes 2 votes I read that the space complexity of Dijasktra is $O(V^2)$ . (http://igraph.wikidot.com/algorithm-space-time-complexity) But how ???? Algorithms dijkstras-algorithm shortest-path space-complexity algorithms graph-algorithm greedy-algorithm + – Hardik Maheshwari asked Jul 5, 2018 Hardik Maheshwari 3.0k views answer comment Share Follow See all 7 Comments See all 7 7 Comments reply srestha commented Jul 5, 2018 reply Follow Share 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 votes 1 votes amitpandey675 commented Jul 5, 2018 reply Follow Share Yeah, when the graph is complete then we use adjacency matrix which gives O(v^2) 1 votes 1 votes Hardik Maheshwari commented Jul 6, 2018 reply Follow Share @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 votes 1 votes Shubham Shukla 6 commented Jul 6, 2018 reply Follow Share @ 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. 1 votes 1 votes Hardik Maheshwari commented Jul 6, 2018 reply Follow Share @Shubham Shukla - The input space is not considered while calculating space complexity. 0 votes 0 votes Shubham Shukla 6 commented Jul 6, 2018 reply Follow Share @ hardik can you show me where it is written.? 0 votes 0 votes amitpandey675 commented Jul 6, 2018 reply Follow Share Both input and extra space taken by the algorithm during its running time is considered during calculating the time complexities 0 votes 0 votes Please log in or register to add a comment.
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). Shinei Nouzen answered Mar 11, 2019 Shinei Nouzen comment Share Follow See 1 comment See all 1 1 comment reply suraj prasad shaw commented Jan 16, 2020 reply Follow Share It is wrong. It will be O(V). 0 votes 0 votes Please log in or register to add a comment.