patternMinor
Why Djikstra's algorithm is said to have $\mathcal{O}(|V|^2)$ complexity?
Viewed 0 times
whydjikstraalgorithmsaidcomplexitymathcalhave
Problem
Djikstra's algorithm assigns some number to non-removed vertex each time it finds a path from removed vertex to it. Number of assignments is $\mathcal{O}(|V|^2)$. However, complexity of assignment is not $\mathcal{O}(1)$, it is $\mathcal{O}(\log s)$, where $s$ is weight of the path from initial vertex to current.
And this means that complexity is $\mathcal{O}(|V|^2\log s)$.
Am I missing something?
And this means that complexity is $\mathcal{O}(|V|^2\log s)$.
Am I missing something?
Solution
Algorithms are usually analyzed under the word RAM model, in which basic operations on machine words cost $O(1)$. Machine words are defined as words of length $\log n$, where $n$ is the size of the input (in bits).
In the case of algorithms on weighted graphs, we could make the further assumption that weights are put in special registers for which "reasonable" arithmetic operations are $O(1)$. This assumption is made implicitly, without any mention of it, since the exact computation model isn't really needed when designing an algorithm, as long as you're not "cheating". It allows using floating point weights, for example.
The computation model serves two purposes:
If we are not careful with the computation model, we could solve PSPACE-complete problems such as TQBF; see here.
One instantiation of the murky class of computation models for weighted graphs is allowing the weights to fit in a constant number of machine words; then we can just analyze the algorithm using the word RAM model. In this case, any weight encountered during Dijkstra's algorithm also fits in a constant number of machine words, since any such weight is the sum of at most $|V|-1$ weights. Therefore in the word RAM model, assignment (as well as addition) costs $O(1)$ rather than $O(\log s)$.
In the case of algorithms on weighted graphs, we could make the further assumption that weights are put in special registers for which "reasonable" arithmetic operations are $O(1)$. This assumption is made implicitly, without any mention of it, since the exact computation model isn't really needed when designing an algorithm, as long as you're not "cheating". It allows using floating point weights, for example.
The computation model serves two purposes:
- To explain what constitutes "cheating", that is, what is not allowed (or rather, what is allow).
- To allow proving lower bounds.
If we are not careful with the computation model, we could solve PSPACE-complete problems such as TQBF; see here.
One instantiation of the murky class of computation models for weighted graphs is allowing the weights to fit in a constant number of machine words; then we can just analyze the algorithm using the word RAM model. In this case, any weight encountered during Dijkstra's algorithm also fits in a constant number of machine words, since any such weight is the sum of at most $|V|-1$ weights. Therefore in the word RAM model, assignment (as well as addition) costs $O(1)$ rather than $O(\log s)$.
Context
StackExchange Computer Science Q#75944, answer score: 6
Revisions (0)
No revisions yet.