マージソートの計算量

質問

データ構造とアルゴリズムのテストでこんな問題が出てきました。

マージソートにおける値の比較回数は、C(n)は次のように表すことができる。C(4)は幾らか。

C(n) = 1 (n = 1のとき)
C(n) = 2 C(n/2) + n (n > 1のとき)

この問題の解答は１２でした。
この問題を解くプロセスを教えていただけませんか？
よろしくお願いします。

回答No.1

asuncion · ベストアンサー

> C(n) = 2 C(n/2) + n (n > 1のとき)

この式にn=4を代入します。すると、
C(4)がC(2)を使って表わせます。

次に、同じ式にn=2を代入します。すると、
今度はC(2)がC(1)を使って表わせます。
C(1)は1であると定義しています。

C(1)からC(2)を求め、C(2)からC(4)を求めてください。