# asymptotics – implementation of d-ary heap vs. implementation of Fibonacci heap Comparisons of Dijkstra performance

Suppose that Dijkstra's algorithm with the priority queue uses a d-ary memory segment. if we adjust d, we can try to get the best runtimes for the algorithm, with d being ~ | E | / | V |.

So, for a | V | fixed, what is the highest possible ratio between this runtime and the Dijkstra runtime using a Fibonacci segment? Where to know the Fibonacci segment: delete_min = O (log | V |), insert / decrease_key = O (1) (damped) and | V | × delete_min + (| V | + | E |) × insert = O (| V | log | V | + | E |).

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

Like trying to follow a solution to provide, but I'm not sure why it reduces to O ($$dfrac {log | V |} {log | E | / | V |})$$, in case 1 where | E | dominates, so Dijkstra with Fibonacci heap is O (| E |), How do we get the ration as O ($$dfrac {log | V |} {log | E | / | V |})$$ while Dijkstra with d-aire is O $$((| V | · d + | E |) dfrac { log | V |} {log d}$$)?