d-ary heap implementation vs Fibonacci heap implementation Dijkstra performance comparions

Question

Let's say that Dijkstra’s algorithm with the priority queue using a d-ary heap. if adjusting d, we can try to achieve the best runtimes for the algorithm with d being $\sim |E|/|V|$.

Then for a fixed $|V|$, what is the largest possible ratio between this runtime and the runtime of Dijkstra using a Fibonacci heap? Where knowing the Fibonacci heap: delete_min = $O(\log |V |)$, insert/decrease_key = $O(1)$ (amortized) and $|V|$ × delete_min + $(|V | + |E|) $ x insert $= O(|V|\log|V|+|E|)$.

On the other hand, d-ary heap implementation : delete_min = $O(\dfrac{d \log|V|}{\log d})$, insert/ decrease_key =$O(\dfrac{\log|V|}{\log d}$), and |V | × delete_min + (|V | + |E|) × insert = $O( (|V|·d+|E|)\dfrac{ \log|V|}{\log d})$.

As trying to follow a provide solution, but I am not sure why it reduces to $O(\dfrac{\log|V|}{\log |E|/|V|})$, in the case 1 where |E| dominates, so Dijkstra with Fibonacci heap is $O(|E|)$. How can we get the ratio as $O(\dfrac{\log|V|}{\log |E|/|V|})$ while Dijkstra with d-ary heap is $O( (|V|·d+|E|)\dfrac{ \log|V|}{\log d}$)?

Answer 1

The crux is right there in the first paragraph of the post.

Let's say that Dijkstra’s algorithm with the priority queue using a $d$-ary heap. We can achieve the best runtimes for the algorithm with $d$ being $\sim |E|/|V|$.

As you have pointed out, the time-complexity of Dijkstra with $d$-ary heap is $O\left((|V|\cdot d+|E|)\dfrac{ \log|V|}{\log d}\right)$. Substituting $|E|/|V|$ for $d$, we see the best time-complexity of Dijikstra with d-ary heap is $O\left((2|E|)\dfrac{\log|V|}{\log|E|/|V| }\right)=O\left(\dfrac{|E|\log |V|}{\log |E|/|V|}\right)$.

In the case 1 where $|E|$ dominates, the ratio of the best time-complexity of Dijkstra with $d$-ary heap to $O(|E|)$, the time-complexity of Dijkstra with Fibonacci heap is $\dfrac{\log|V|}{\log |E|/|V|}$ (ignoring some constant factor), which takes its maximum value when $|E|$ takes its minimum value, $|V|\log |V|$. Hence we get the ratio $\dfrac{\log|V|}{\log\log|V|}$.