混乱しています。最悪の場合の実行時間にはBigOを使用し、最良の場合にはΩを使用すると思いましたか？誰か説明してもらえますか？
そして、（lg n）は最良のケースではありませんか？そして（nlg n）は最悪のケースですか？それとも私は何かを誤解していますか？
サイズnのヒープでのMax-Heapifyの最悪の実行時間がΩ（lgn）であることを示します。（ヒント：ノードがn個あるヒープの場合、ルートからリーフまでのパス上のすべてのノードでMax-Heapifyが再帰的に呼び出されるようにするノード値を指定します。）
編集：いいえ、これは宿題ではありません。練習していて、これには答えの鍵があります。 http://www-scf.usc.edu/~csci303/cs303hw4solutions.pdf問題4（6.2-6）
編集2：それで私はビッグOとΩについてではない質問を誤解しましたか？
ケースとバウンドを区別することが重要です。
アルゴリズムを分析する場合、最良、平均、および最悪が一般的な関心事です。
上限（O、o）と下限（オメガ、オメガ）は、シータとともに、関数の一般的な境界です。
「アルゴリズムXの最悪の場合の時間計算量はO（n）」と言うとき、入力を最悪の場合の入力に制限するときのアルゴリズムXのパフォーマンスを表す関数は、上からある線形関数によって漸近的に制限されると言います。 。最悪の場合の入力の下限について話すことができます。または、平均的な、または最良の場合の動作の上限または下限。
ケース！=バインドされています。とは言うものの、「最悪の場合は上」と「最高の場合は下」はかなり賢明な種類のメトリックです...これらはアルゴリズムのパフォーマンスに絶対的な限界を提供します。他の指標について話せないという意味ではありません。
更新された質問に回答するために編集します。
質問では、Omega（lg n）が最悪の場合の動作の下限であることを示すように求められます。言い換えると、このアルゴリズムが入力のクラスに対して実行できるのと同じくらい多くの作業を実行する場合、実行する作業の量は、漸近的に、少なくとも（lg n）と同じ速さで増加します。したがって、手順は次のとおりです。（1）アルゴリズムの最悪のケースを特定します。（2）最悪の場合に属する入力のアルゴリズムの実行時間の下限を見つけます。
これが線形検索を検索する方法の図です。
線形検索の最悪のケースでは、ターゲットアイテムがリストにないため、リスト内のすべてのアイテムを調べてこれを判断する必要があります。したがって、このアルゴリズムの最悪の場合の複雑さの下限はO（n）です。
注意すべき重要な点：多くのアルゴリズムでは、ほとんどの場合の複雑さは、共通の関数セットによって上下から制限されます。シータが適用されることは非常に一般的です。したがって、いずれにしても、Omegaの場合とOの場合とで異なる答えが得られない場合があります。
実際には、最悪の場合の複雑さよりも速く成長する関数にはBig Oを使用し、最悪の場合の複雑さよりもゆっくりと成長する関数にはΩを使用します。
したがって、ここでは、最悪の場合の複雑さがlg（n）よりも悪いことを証明するように求められます。
Oは上限（つまり、最悪の場合）Ωは下限（つまり、最良の場合）
この例では、max-heapifyの最悪の入力（最悪の入力は逆順の入力だと思います）では、実行時間の複雑さは（少なくとも）lgnでなければならないということです。したがって、Ω（lg n）は、実行の複雑さの下限であるためです。