On specifying complexity guarantees

[akrzemi1]

In the current version f the paper the "complexity" for dijkstra_shortest_paths is specified as follows.

This has some issues in the context of the Library specification, whose goal is:

• to determine the trade-off between the implementation freedom and the guarantees that the users will get;
• not to suggest any implementation strategy.

One. As a user, programming potentially against multiple implementations, I need to have one complexity guarantee: not two. If you want to allow the implementations to freely choose between the priority queue and the and the Fibonacci heap implementations, then the guarantee for me is:

Complexity: Either 𝒪((|E| + |V|) log |V|) or 𝒪(|E| + |V| log |V|), depending on the implementation.

Two. The complexity specification in the Standard Library is usually more specific than just the Big-O notation. Consider:

https://eel.is/c++draft/func.search.bm#8:

Complexity: At most (last - first) * (pat_last_ - pat_first_) applications of the predicate.

(in terms of the number of calls of the predicate)
https://eel.is/c++draft/binary.search#4:

Complexity: At most log₂(last - first)+𝒪(1) comparisons and projections.

(in terms of comparisons and projections)

In the case of dijkstra_shortest_paths, it is not clear what operations are deemed the "dominating" ones. I am not a graph expert, but I read here that the dominating operations are:

• push a vertex into the priority queue,
• pop the minimum-distance vertex off the queue,
• decrease the vertex distance in the priority queue.

So, in order to describe the complexity more accurately, you have to expose the implementation strategy to the users. Which leads to the next question.

Three. Should the users be able to control which implementation strategy is chosen? Is the Fibonacci Heap universally better than any other implementations? If not, it may make sense to expose this control. Whatever the answer, the discussion of this subject should be included in the paper.