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

設問5の②について質問です。

降順にソートされている場合のheap_make(A)の計算量がO(N)となっています。
しかし、どの部分木をとってもヒープ条件を満たしており、heap_correct()が再帰的に呼び出されることはありません。ゆえに、計算量はheap_correctが呼び出される回数のO(2/N)だと思うのですがどうですか？

計算量がO(N)だとしたら、すべてのノードに対してheap(correct)を適用していることになると思います。