『Merge Sort の計算時間』

【問題】

Merge Sort の計算時間問題です。

T(n)=T([pn])+T(【(1-p)n】)+n-1 ;
　0＜p＜1、n∈N,

where
［x］= flooring function of x
　 (The greatest integer ≦x) and

【x】= ceiling function of x
　 (The least integer ≧x),

【問題１】

T(1)=1; p= 1
―
2 のとき、

T(n)を求めなさい。

【問題２】

T(1)=1; p= 1
m+1 ,m∈N (自然数) のとき、

T(n)を求めなさい。

【問題３】

T(n)=T([pn])+T(【(1-p)n】)+nc+d ;
0＜p＜1, T(1)=a, pが有理数のとき、
T(n)をもとめなさい。

【問題４】

T(n)=T([pn])+T(【(1-p)n】)+a_r*n^r+a_r-1*n^r-1+...+a₀ ;
0＜p＜1, T(1)=a, pが有理数のとき、
T(n)をもとめなさい。

【おまけ】

問題4からpが無理数のとき、T(n)をもとめなさい。