[解決済み] T(n) = 2T(n/2) + O(n) からO(nlogn)を得る方法

質問

アルゴリズムを勉強しているのですが、マスターの定理を使わずにO(nlogn)を得るという質問を受けました。

O(nlogn)を求めるのに苦労しています。

T(n) = 2T(n/2) + O(n) から O(nlogn) を求める数学的な方法をご存知の方はいらっしゃいますか？

サンクス

解決方法は？

再帰木を描画します。

木の高さは対数nになる

各レベルのコストは、n の一定倍となる。

したがって、総費用はO(nlogn)となる。 http://homepages.ius.edu/rwisman/C455/html/notes/Chapter4/RecursionTree.htm

そして、その気になればいつでも帰納法で証明できるのです。