計算量の下界の計算

質問

ある論文中の回路計算量の下界を求めようと思うのですが、どうも計算がうまくいかないので知恵をお貸しください。

l=√(k)(切り捨て)
p=10√(k)log_{2}n(切り上げ)
m=(p-1)^{l}*l!
この時、size(C)・m^2・(n-l-1)Choose(k-l-1)≧(n)choose(k)
という式からsize(C)の下界がn^{Ω(√(k))}と定まるらしいのですが、この導出がわからないのです。
Ωは下界オーダーの記号です。
size(C)≧～という式にしてこの右辺がn^{Ω(√(k))}で表せる式になればよいと思うのですがいまいちうまくいきません。

お分かりの方がいらっしゃいましたら教えていただけると幸いです。
よろしくお願いします。

回答No.2

Tacosan

m をどう処理すればいいかちょっと見えないんだけど,
size(C)・m^2・(n-l-1)Choose(k-l-1)≧(n)choose(k)
から
size(C)・m^2 ≧ n! (k-l-1)! / [(n-l-1)! k!] = (n choose (l-1)) / (k choose (l-1))
になるかな? n choose k で k が非常に小さいときに上下界が出たはずなので, それで置き換えると右辺が簡単になるかもしれません.

回答No.1

rabbit_cat

見難いのと面倒なので、実際には計算してないですが、
多分、階乗をスターリングの公式で抑えて、なんか計算してると出るんじゃないですかね。