漸近的な上限と下限を見つけることは？

Question

T（n）が小さいnに対して一定であると仮定すると、この関数の解をどのように見つけることができますか？

これまでのところ、私は機能全体を表現する方法を見つけることができません。手伝ってくれませんか？私は本当に理解したい。

Answer 1

nが偶数であり、それがT(1) = T(0) = 0であると仮定します。 nでも、T(n) = Theta(n log(n))ためので

T(n)/2 = log(n) + log(n-2) + ... + log(2) 
     = log((n/2)! * 2^n) 
     = n log(2) + log((n/2)!) 
     = n log(2) + n log(n) - n + O(log(n)) (Stirling's approximation) 

。

n奇数の場合、T(n-1) < T(n) < T(n+1)に注意し、同じ漸近線を得ることができます。