離散フーリエによる時間計算量

質問

分割統治法を用いて、N点離散フーリエ変換を計算するとき（高速フーリエ）、その時間計算量T(N)＝２T(N/2)＋Nを再帰的に代入して次数を下げていくことにより、Nを大きくしたときの漸近的な振る舞いは
T(N)＝O（Nlog_2 N）となることを示そうと、代入を試みてやってみたのですが、まず
T(N)＝O（Nlog_2 N）の右辺は何を意味しているのか分からず、またどのようにそれを導けばいいのか検討がつきません。
ヒントを教えてもらえないでしょうか？

回答No.1

Tacosan

f(n) = O(g(n)) と書いたら「十分大きな任意の n に対して f(n) ≦ c g(n) を満たす (n によらない) 定数 c が存在する」ということを意味します.
だから, 「十分大きな n に対し T(n) ≦ cnlog n を満たす c が存在する」ということを示せば OK.
そのために「再帰的に代入する」わけでしょ?

補足

T(N)/ｎlog_２ N　→　C（ｎ→無限大）を示せればいいということですか？