演算法課本題目 (Exercise 4.1-5) : 求 Big-O

CORMEN聖經本的 Exercise 4.1-5，花了我一整個晚上在解

期間還受不了上網偷拜 Google 大神，因為不會輸入 floor 的符號，一直找不到相關題目的解

後來終於解出來了，發哥卻在旁邊說，"這種題目你怎麼沒上網辜？"

我就照他的指示，輸入關鍵字 "2T(floor(n/2)"，

只出現短短5項連結，其中有一個就是別人的解！

偉哉，發哥！


不過辜出來的解最後有錯，

在此幫忙勘誤一下：

因為前提為 34*c*lgn - n*(0.3*c-1) <= 0
且 34*c*lgn >= 0
=> - n*(0.3*c-1) <= 0
=>   n*(0.3*c-1) >= 0
=>      0.3*c-1  >= 0
=>          c    >= 3.3~

所以他令 c = 1 是錯的

後來我推導了一下，實際上 c 必須大於等於 1 / lg(6/5) ~= 3.802

如果令 c = 4，n 必須大於等於 2048 才符合條件。



這時，如果有講義上的 Hint，n 不必到2048以上才符合條件：

Hint: T(n) = a n lg n - b lg n - c