2.4.5 線性對數算法的性能
性能名額很好地描述了同類算法的共同行為。為了更好地闡述算法在實踐中的行為，我們定義了一個函數t(n)，用于表示算法解決樣本規模為n的問題所需要的時間。分治法是解決問題的一個高效方法，它将規模為n的問題劃分成（大緻相等的）兩個規模為n/2的子問題，并通過遞歸解決問題。這些子問題會通過線性時間方式合并在一起來解決原先規模為n的問題。使用數學表達式可以表示為：
也就是說，t(n)包括了解決兩個子問題和歸并結果的費用，其中歸并結果的費用不超過線性時間（即c*n）。在等式的右邊，t(n/2)是解決規模為n/2 的問題的時間，按此邏輯推理，t(n/2)可以表示為：
是以最初的等式可以寫為：
如果再擴充一層，可以得到：