想請教此題
The comparison-based sorting algorithm on n data requires Ω(nlgn) time.
我的理解
根據Ω的意思，此題應該是要證comparison-based sorting 至少(最好情況)nlgn的複雜度
而解答上寫在worst case時至少需要h(樹高)次的比較
再來n個數有n!種可能性的排序，每個葉存一個，至少要有n!個葉
h高度的葉最多為2^h個
我的問題是解答上先說是worst case，但題目不是要最好情況下嗎？
如n=3，a,b,c三數比大小
最好情況不是a>b成立b>c成立 => a>b>c
這樣嗎？
有點不太理解解答的意思，謝謝
另外再請教林立宇老師課本上證明lg(n!)=Θ(nlgn)跟有些題目都沒有取c
定義上是要取c，是可以省略還是必須寫？