• all input items are black boxes (ADTs)
• the only operations allowed are comparisons(<, ≤, >, ≥, ...)
• time cost = #comparisons

Decision Tree(決策樹)

Any comparison algorithm can be viewed/specified as a tree  of  all  possible comparison outcomes & resulting output, for a particular n

example, binary search for n= 3

Decision tree	Algorithm
internal node	binary decision
leaf	output (the algorithm is done)
root-to-leaf path	algorithm execution
path length (depth)	running time
height of tree	worst-case running time

Searching Lower Bound

• n preprocessed item
• 最差狀況下, 從中搜尋需 Ω(lgn) 時間

#證明

1. 決策樹為一二元樹 
2. #leaves ≥ #possible answers ≥ n
3. height ≥ lgn

Sorting Lower Bound

• 最差狀況下, Ω(nlgn)

#證明

1. 決策樹為一二元樹
2. #leaves ≥ #possible answers = n!
3. height ≥ lg(n!) = Ω(nlgn)

Linear-time Sorting(integer sorting)

• assume n keys sorting are integers ∈ 0, 1, 2, ... ,k-1 (fitting in a word)
• can do more than comparison
• for k, can sort in O(n) time

Counting Sort

通俗地理解，例如有10個年齡不同的人，統計出有8個人的年齡比A小，那A的年齡就排在第9位，用這個方法可以得到其他每個人的位置，也就排好了序

L = array of k empty lists     //O(k)
for j in range n:              //O(n)
   L[key(A[j])].append(A[j])

output = []
for i in range k:              //O(n+k)
   output.extend(L[i])

#複雜度

Θ(n+k)

Radix Sort

1. imagine each integer in base b, d= logbk digits
2. 從最小位數開始, 進行排序(via Counting Sort)
3. 當以最大位數進行排序完成後即為結果

#複雜度分析

每一位數: O(n+b)  //via Counting Sort
總時間: O((n+b)d) = O((n+b)*logbk)
當 b = n 時有最小值, O(n*lognk) = O(nc)