まず最初に、私はこのサイトを初めて使用するので、何か間違ったことをしている場合はお知らせください。次の証明について助けが必要です。私は答えを探しているのではなく、単にガイダンスを探しています。
Θ の定義を使用して、次を証明します。klgk = Θ(n) の場合、k = Θ(n/lgn) です。
私の教授は、k < n から始めるように言いました。次に、両辺の対数を取ると、lg(k) < lg(n) が得られます。次に、両辺に k を掛けて、最終的に k*lgk < k*lgn を得ます。ここから、k*lgn <= c2*n と言え、両辺を lgn で割ると、k <= c2 * (n/lgn) となります。したがって、k = O(n/lgn) です。最初に k < n と言えるのはなぜですか? 何か不足していますか？助けてくれてありがとう。