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

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}$$)?

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|}$$.