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

https://www.ap-siken.com/kakomon/30_aki/pm03.html

問題文の後半の〔ウェーブレット木の評価〕において、『定数時間』というフレーズが使われています。
定数時間はO(1)のことであり、設問4では定数時間に該当する計算量がO(N)となっています。O(N)は線形時間であり、定数時間ではないと思うのですが、問題文の『定数時間』とは何を示しているのでしょうか？

ここでの定数時間とは深さに対応したビットを識別して
左右の木に分ける動作1回分の事を指してると思われます。
文字の種類が何種類だろうが文字列が何文字だろうがある1ビットを検査して
0か1か判断してるだけなので計算量は変わらないという事だと思います。
その定数時間に文字数Nと1文字ごとに分類しないといけない回数log2(σ)をかけた数字が
構築時間になるので、定数時間をαとするとα×N×log2(σ)
オーダ表記法は係数を省くのでO(Nlog(σ))が解答になったと考えられますがいかがでしょうが？
ちょっと話は逸れますが何故かこの問題では対数の底を省いていないのが気になります。

ありがとうございます！
定数時間は別の処理のことを言っているんですね。腑に落ちました。