시간 복잡도는 버켓의 갯수 B에 영향을 받는다. B는 O(logC) 이고, C는 키의 최댓값과 최솟값의 차이이다. 32bit 정수를 대상으로 동작한다면 최대 32라고 봐도 된다.
위키피디아에 의하면 insert는 O(B), extract-min은 amortized O(1), decrease-key도 amortized O(1)이라고 한다. 이대로 다익스트라 알고리즘에 적용한다면 시간복잡도가 O(|V|+|E|)가 될 것이다.
하지만 보통 decrease-key 를 구현하지 않는 것 같다 (참고 구현체: https://github.com/iwiwi/radix-heap). 그렇게 insert와 extract_min으로만 다익스트라 알고리즘을 구현한다면 O(|E|*B)가 될텐데, 이것은 그냥 바이너리 힙을 썼을때의 O(|E|log|V|)보다 빠르기 힘들다.