T(n)=2T([n/2])+nの解がΩ(nlgn)であることを証明せ

質問

T(n)=2T([n/2])+nの解がΩ(nlgn)であることを証明せよ。
ただし、[n/2]は床関数です。
証明の途中で詰まってしまい、どうすればいいのか分からず、質問させていただきました。

(証明)
T(n)≧c(n+b)lg(n+b)と推測する。
T(n)≧2c([n/2]+b)lg([n/2]+b)+n
　　≧2c(n/2+b-1)lg(n/2+b-1)+n
　　＝c(n+2b-2)lg(n+2b-2)-c(n+2b-2)+n
　　＝c(n+2b-2)lg(n+2b-2)-(c-1)n-2(b-1)

これだと最終的にT(n)≧c(n+b)lg(n+b)を導けません。
どうすればよいのでしょうか。
ご教授ください。

回答No.2

Tacosan · ベストアンサー

はい, 間違い.
c は正でないといけないですが, b に対しては特に条件はありません (負でもかまわない). さらに, c が「十分に大きい定数」ということはありません (正でありさえすればよい). もう一度, きちんと確認してください.
今の場合, b=2, c=0.5 とおけば「十分大きな全ての n」で T(n) ≧ c(n+b) lg(n+b) がいえるはず.

お礼

丁寧に説明してくださり、本当にありがとうございます。
もう1度、教科書等を確認したいと思います。
本当にありがとうございました。

回答No.1

Tacosan

「最終的に何を示すのか」はきちんとつかめていますか? 例えば「T(n)≧c(n+b)lg(n+b)と推測する。」と書かれていますが, ここに現れる b や c (や n) についてどのような制約があるのか, あるいはどのような条件のもとでこの不等式が満たされればよいのか, ちゃんと理解していますか?
ヒント: 「T(n) = Ω(n lg n)」であることは「全ての b, c, n に対して T(n)≧c(n+b)lg(n+b) が成り立つこと」＊ではない＊.

補足

bとcは0より大きい定数で、cは十分に大きい定数でないといけない。
最終的にT(n)≧cnlgnを示せれば、T(n)＝Ω(nlgn)であることを証明できると考えています。
教科書を見直して考えているのですが、自信がないです。