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 回答日時： 2010/01/06 18:44

はい, 間違い.

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

この回答へのお礼

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

お礼日時：2010/01/06 19:43

No.1 回答者： Tacosan 回答日時： 2010/01/06 16:09

「最終的に何を示すのか」はきちんとつかめていますか? 例えば「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)であることを証明できると考えています。
教科書を見直して考えているのですが、自信がないです。

補足日時：2010/01/06 17:12