応用情報技術者 試験情報＆徹底解説

平成30年秋  午後問3  設問4に関して質問させていただきます。

以下、応用情報技術者試験ドットコムの解説をもとに説明させて頂きます。

設問4  ケに関して、
解説では、各ノードでの計算量はO(N)になると書かれています。
上記条件でウェーブレット木を構築するとき、対象となるノードの数はσ-1となるため、
ウェーブレット木の構築時間は、O(N・σ)になると考えています。

なぜO(N・log_2(σ))が構築時間となるのでしょうか。
解説を頂けたら幸いです。