CODEWITHSUNDEEP
complexity-theorytime-complexitydijkstraasymptotic-complexity
Robert777
Robert777

Reputation: 801

Implement Dijkstra's Algorithm with a d-ary heap

As you can see in this link: http://en.wikipedia.org/wiki/D-ary_heap#Applications It says in Wikipedia that the optimal choice of d is d=m/n (it leads to a total time complexity of O(m logm/n n) )

It seems to me that this guess was pulled out of thin air. Is there a simple way of proving (or even explaining) that this is indeed the optimal d ?

Thanks in advance

Upvotes: 1

Views: 2297

Answers (1)

Origin
Origin

Reputation: 2017

From the explanation itself you can deduct that you have n delete min operations each requiring O(d log(n)/log(d)) and m decrease priority operations of O(log(n)/log(d)). The combined work is then (m*log(n)+n*d*log(n))/log(d).

If you fill in the suggested d value, the global behavior is as stated O(m*log(n)/log(d)). If you take any other d, one of the terms is bigger then the average, resulting in an increased complexity.

Upvotes: 3

Related Questions