허프만 코드를 생성하는 알고리즘이 효율적인가? 알고리즘 3-1로 돌아가서 살펴보면 루프는 인코딩하려는 문자 개수가 n일 때 정확히 n - 1번 실행된다. 이유는 다음과 같다. 각 반복 단계에서 2번의 추출과 한 번의 삽입 작업을 수행하여 우선순위 큐의 크기가 1씩 감소한다. 반복은 우선순위 큐에 원소가 오직 하나만 있을 때 멈춘다. 우선순위 큐는 인코딩하려는 문자를 하나로 세어 초기에는 n개의 원소가 있고 n - 1번 반복한 후에는 큐의 크기가 1이 되며 하나의 원소를 반환한다.

다음으로 삽입과 추출을 설명하면, 알고리즘 3-2에서 삽입은 기껏해야 힙의 깊이만큼 반복한다. 힙은 완전 이진 트리라서 한 노드에서 부모 노드까지 가려면 2로 나누어야 하고 최상위 레벨까지 레벨마다 반복하여 루트 노드에 도달하므로 깊이, 즉 반복 횟수는 트리 크기의 이진 로그인 lgn이 된다. 이와 비슷하게 알고리즘 3-3에서도 추출은 힙의 깊이만큼 반복해야 한다. 전체적으로 허프만 코드 생성은 2번의 추출과 1번의 삽입을 n - 1번 반복해야 하는데, 이때 복잡도는 O((n - 1)3lgn)으로 O(nlgn)이 된다.