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)を導けません。
どうすればよいのでしょうか。
ご教授ください。
お礼
有難うございました