0
$\begingroup$

As per my understanding. The space complexity will be O(V). An array of V nodes will be created which in turn be used to create the Min heap.

But this link is stating that It is O(V^2)? I don't understand how it can be O(V^2)?

I have search the same topic in the Book entitled Introduction_to_Algorithms by Thomas H. Cormen but still not able to find the answer. I Don't understand what I am missing.

$\endgroup$
0

1 Answer 1

3
$\begingroup$

Dijkstra's algorithm can be implemented in many different ways, leading to resource usage. The page you link gives the resource usage the implementations in the specific library being described.

I can't think of a way of implementing Dijkstra to use $|V|^2$ space, but I would note two things.

  1. $O(\cdot)$ only gives an upper bound. Even if the implementation actually uses space $O(|V|)$, it's not wrong to say that it uses $O(|V|^2)$ or even $O(2^{|V|})$, just as it's not wrong to say that I earn less than a billion dollars a year. However, it would be unusual to say $O(|V|^2)$ if it was easy to prove the stronger bound of $O(|V|)$ (I also earn less than a million dollars a year), and it is easy to prove $O(|V|)$ for most implementations of Dijkstra.

  2. The page quotes the running time as $O(s|E|\log|E|+V)$, where $s$ is the number of sources being considered. It's easy to imagine space usage of $O(s|V|)$ so maybe they wrote $O(|V|^2)$ since $s\leq|V|$. But that would also be strange, given that the quoted running time shows they're not afraid to use $s$.

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.