我們将算法執行時間的增長率描述為一個與輸入問題樣本規模相關的函數。使用這種方法描述算法性能會比較抽象，因為它忽略了大量的細節問題。是以，在使用這種方法時，需要對抽象背後的細節有一個清醒的認識。程式都必須運作在某個平台上，在這裡，廣義的平台定義包括：
運作程式的計算機，包括CPU、資料緩存、浮點運算單元（FPU）以及其他晶片特性。
程式編寫所使用的程式設計語言、編譯器/解釋器以及用于生成代碼的優化設定。
作業系統。
其他背景程序。
改變上述組成平台的任何條件都隻會對程式的執行時間造成常量級别的影響，是以根據之前提到的漸近等價原理，我們會忽略由平台一緻性所導緻的性能差異。
為了讓函數增長率的讨論擁有更為具體的場景，我們會簡要地讨論一下順序搜尋算法，關于這個算法的細節稍後會在第5章講到。所謂順序搜尋，就是在一個包含n個（n≥1）互異元素的清單中順序地進行搜尋，直至找到想要的值v。我們暫時假設：
清單中的n個元素各不相同。
待查找的元素v一定在清單中。
清單中每個元素都有可能是待查找的元素v。
為了了解順序搜尋算法的性能，我們必須知道待檢查的元素總數的“平均值”是多少。由于已知v肯定在清單中，并且每個元素都有可能為v，是以待檢查的元素平均數E(n)為：n個元素總共需要檢查的個數總和除上n。其數學表示為：
由此可見，在上述前提下，順序搜尋算法對于n個互異元素所組成的清單需要檢查大約一半數量的元素。如果清單中的元素數量翻倍，那麼順序搜尋算法需要檢查的數量也會大緻翻倍。是以，可以将順序搜尋算法期望的檢查次數視作一個關于n的線性函數，即“大約”為c*n（其中c是常數，這裡c = 0.5）。性能分析的一個基本的觀點認為，常數c從長遠角度看是不重要的，因為影響性能的最重要因子是問題樣本的規模n。随着n越來越大，錯誤率就會如同下式一樣變得不再重要：
實際上，約等式兩側的比率近似趨向于1，即：
當然，在n較小時，估算中的誤差會比較大。在這樣的使用環境下，順序搜尋期望查找的元素數量增長率是線性的。也就是說，當樣本規模很大時，我們會忽略常數乘法常量，而主要關注樣本的規模。
依據增長率這個抽象的概念選擇算法時，需要牢記的是：
常數的重要性
這就是我們使用超級計算機并定期對其更新的原因。
樣本規模n并不總是很大
在第4章我們将會看到，快速排序算法執行時間的增長率要低于插入排序算法執行時間的增長率。但是在相同平台下，對于小資料集，插入排序算法表現得要比快速排序算法更好。
算法的增長率決定了算法在逐漸增長的資料集上的性能表現。下面将通過一個更為複雜的例子來解釋如何應用這個基本原理。
考慮通過一個特定的分類任務來對四種排序算法進行評估。下述性能資料通過對n個随機字元串進行排序來生成，n的取值範圍為1-512。對于每個n的取值，我們都将進行50次實驗，并且舍棄掉最好和最壞的實驗結果。圖2-1展示了剩餘48次實驗的平均執行時間（機關：n的資料樣本上的性能。當然，随便猜想出這樣的一個函數是不切實際的，是以我們借助已有的商業軟體對結果采用統計方法進行了回歸分析，并且根據結果描繪出了一條趨勢線。趨勢線與實際資料的拟合度設為R2，取值為0-1。R2越趨近于1，表示拟合度越高。例如，R2 = 0.9948表示隻有0.52%的機率趨勢線和資料不拟合，這是由資料的随機變化而導緻的。
第四種排序算法很明顯是四種算法中最差的。根據電子資料表上描繪的512個資料點，與其性能相符合的趨勢線是：
可以看到，R2的值非常接近于1，說明這是一個非常精确的預測。第二種排序算法在給定的資料集上性能最好。其性能可以用如下的趨勢線來描述：
第二種排序算法起初隻是比第三種排序算法的速度稍快，但最後它比第三種排序算法快了10%。第一種排序算法表現出了兩種不同的性能特征。當資料集中的字元串數量不超過39個時，其性能表現為：
但是，當資料集中的字元串達到40個或者更多時，其性能表現為：
上述表達式中的系數完全取決于算法運作的平台。就像之前描述過的那樣，這些附帶的差異并不重要。n的長期變化趨勢支配着這些算法的性能。事實上，圖2-1中采用了兩個不同規模的資料集來诠釋算法性能，可以看到，隻有當資料集的規模n變得足夠大時，算法之間的差異才變得明顯。
算法設計人員常常會努力地探索和了解算法之間的性能差異。第一種排序算法展現了Linux 2.6.9核心中快速排序算法qsort的性能。在閱讀快速排序算法的源代碼時（這些代碼可以在任何Linux的代碼庫中找到），我們注意到了這樣的注釋：“這個快速排序例程由Bentley和McIlroy設計”。Bentley和McIlroy（1993）描述了如何針對不同的問題規模（如規模小于7、在8和39之間以及達到40或者甚至更大），采用不同的政策對快速排序進行優化。實驗結果表明，這個隐藏的優化手段非常有效。
圖2-1：小資料集上四種排序算法的比較結果