[解決済み] 回帰式 T(n) = 2T(n/2) + Θ(1) を代入して解きます。

質問

ということで、O(n)であることは間違いないのですが（でも違うかも？）、代入でどう解くのでしょうか？

T(n) <= c * nとした場合、帰納法はどうなりますか？

どのように解くのですか？

まず、Θ(1)=kがある定数であることを明確に仮定したい。

次に、代入法を用いて進めると、次のようになります。

 T(n)=2T(n/2)+Θ(1)
     =2T(n/2)+k
     =2{2T(n/4)+k)+k
     =4T(n/4)+3k
     =...
     =n.T(1)+(n-1)k
     =n.k+(n-1)k
     =2nk-k
     =O(n).

とした場合 T(n) <= c * n T(1)から始めて、T(n)が正しいことを仮定し、T(n)の仮定を使ってT(n+1)が正しいことを示すようにしなければなりません。

ところで、あなたの仮定は正しかったのですね。