4
$\begingroup$

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?

$\endgroup$
9
  • 2
    $\begingroup$ What you're missing is the computation model used to analyze the algorithm, in which operations on machine words have unit cost. Unfortunately this issue is usually swept under the rug. $\endgroup$ May 27, 2017 at 13:38
  • $\begingroup$ @YuvalFilmus, ah, that's the case. But for real computer it does matter even in unweighted graph. $\endgroup$
    – rus9384
    May 27, 2017 at 13:47
  • 1
    $\begingroup$ Yes, but a real computer does perform operations on machine words - that's how CPUs operate. $\endgroup$ May 27, 2017 at 13:51
  • $\begingroup$ @YuvalFilmus, when numbers become huge, bigintegers are usually used and their speed depends on length. $\endgroup$
    – rus9384
    May 27, 2017 at 13:53
  • 1
    $\begingroup$ This is the usual hidden assumption. $\endgroup$ May 27, 2017 at 14:48

2 Answers 2

3
$\begingroup$

tl;dr- The idea that setting a value has $\mathcal{O}\left(\log{s}\right)$ complexity follows from a presumed model for numeric data where numbers require $\log{x}$ bits for representation. This isn't the case in most real-world implementations nor in general, so it isn't reflected in common descriptions of algorithm complexity.

However, the expression given in the question seems valid when the presumed data model is used. As such, I'd characterize this expression as implementation-specific; it's more precise when applicable, but it's only applicable when the relevant data model is used.

Intro

It sounds like you're assuming a data model for numeric values where values start at $0$, then each bit expands the range, e.g. as in common binary notation. I'll assume that you handle floating-point extensions in a similar manner, e.g. $0.25$ in decimal is stored as 0.01 in the data model, while $\frac{1}{3}$ would require infinite bits to precisely represent.

In binary, we can distinguish $2^{n_{\text{bits}}}$ of numbers given $n_{\text{bits}}$ of storage. Further, this grows with $x$ as $x$ gets larger if we pin the data-zero to numeric-$0$. So, you could say that the complexity of a value $x$ is then $\log_2\left(x\right)$, which is proportional to $\log\left(x\right)$.

The problem with this logic is that you're presuming a data model for numeric values that's (1) not usually true in implementation nor (2) logically optimal. I'll try to comment on (3) the general problem.

(1) Not true in practice

In most common implementations of algorithms like this, primitive datatypes are used. Such datatypes store the same number of bits regardless of the numeric interpretation of their value.

In these cases (which is most cases), the complexity simply doesn't grow with the value of the weights.

(2) Not true in the general case

If only (1) were the issue, it'd seem like an implementation thing, right? But $\log{\left(x\right)}$ isn't logically true either.

The core problem is that it presumes a numeric model where you start at zero and add bits to represent larger values. While that seems like a sensible approach, it's by no means fundamentally the only reasonable way to store data.

For a practical example, consider a system where weights might be a multiple of $\pi$. To store $\pi$ in the presumed data model, you'd need $$\log{\infty}=\infty$$ bits. That's obviously not possible. But, you can use algebraic logic (think Mathematica) with more abstract data types to bridge the gap.

(3) The general problem

In general, the computer needs to do two things:

  1. Keep expressions for total of path distance.

  2. Be able to compare those expressions to determine if one's larger than the other.

Neither of these require that the numbers be stored in a format with $\mathcal{O}\left(\log{s}\right)$ complexity. For example, consider someone asking a StackExchange question like this:

What's larger:

  1. the distance from Washington DC to Maryland; or

  2. the distance from Earth to the edge of the observable universe to the googolplexth power to the googolplexth power.

In answering this question, do you need $\log{\left(\left(\left[{r}_{\text{universe}}\right]^{{10}^{\left({10}^{100}\right)}}\right)^{{10}^{\left({10}^{100}\right)}}\right)}$ of storage in your brain? Or, if they asked about volumes or something else that involves $\pi$, does your brain need infinite data storage?

The answer's obviously no; you have comparison methods that aren't based on the presumed model with $\log_2\left(x\right)$ of storage needed. Likewise, a computer program shouldn't need to use that storage model, either.

Conclusion

We don't attribute $\mathcal{O}\left(\log{s}\right)$ complexity to numeric data because that characterization follows from a model that's neither true in general nor used in practice.

If you do want to include that component in your complexity assessment of an algorithm, you'd need to qualify the complexity claim with the fact that you're considering a special case of the algorithm which uses the presumed data model.

$\endgroup$
2
  • $\begingroup$ Okay, I understood. If it depends on data type, we simply think that operations take constant time, which is (of course) not achievable in real world. $\endgroup$
    – rus9384
    May 27, 2017 at 22:44
  • $\begingroup$ @rus9384 Yeah, that's about right. I mean, when your computer crunches numbers, most of those operations are constant-time due to how the CPU's designed, though they wouldn't be if a CPU used the data types that you're proposing. It's much uglier with abstract data types - for example, if an abstract number is based on a halting problem and you need to compare it to a simple number, you can't be sure that the operation will ever finish. $\endgroup$
    – Nat
    May 27, 2017 at 22:47
6
$\begingroup$

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:

  • 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)$.

$\endgroup$
2
  • $\begingroup$ I think your last paragraph comes closest to an answer. Suppose we ignore the machine words thing altogether and just count bits. Then the size of the sum of a weight is certainly no more than the size of the largest vertex label plus the size of the largest weight (measuring both labels and weights in bits, as above). But we also have to measure the size of the problem in bits, and the size of the problem is the total size of all the weight sizes plus the total size of all the edge specifiers, which must be somehow related to the total size of all the vertex labels... $\endgroup$
    – rici
    May 27, 2017 at 23:55
  • $\begingroup$ ...At the end of all those complications, we're going to end up adding $log w$ and $log V$ terms to both the computation time and the problem size, where they will roughly cancel each other out, although the maths will be insanely irritating because there are two different $log$ terms to deal with. That's the basis of the RAM model simplification: that since we classify complexity in terms of the problem size, it is not terribly inaccurate, and a lot simpler, to count objects and count adds rather than counting bits. $\endgroup$
    – rici
    May 27, 2017 at 23:58

Your Answer

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

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