如果能夠事先得知未來的所有 update，設計出對應的演算法，這就叫做「離線演算法」。顯然在能夠得知未來 update 的情形下，總是可能得出更有效率的演算法。這給予我們另一種能夠刻畫線上演算法效能的一種方式：如果對於一組擁有 m 次更新的輸入來說，若將 update 逐一餵給一個線上演算法，其總時間複雜度為 A、而最好的離線演算法所需要的時間複雜度為 B 的話，我們就說這個線上演算法是 A/B-competitive 的。
在這樣的評估方法中，我們不在意「絕對的效率」，有些特定的輸入可能會導致你的程式花費 O(m^2) 時間、有些可能很有效率，只要 O(m) 時間。但是在特定的競爭力保證下，我們可以說不管程式跑得快或跑得慢，它與最好的離線演算法不會差距太大。
經典的競爭力分析可以用在以下三個題目：
一個滑雪場每天租滑雪板要花 X 元。如果你購買滑雪板要花 Y 元。悲慘的是，你事先不知道你會去滑雪幾天XD 請問你有沒有一套租雪版的策略，使得花費的錢「相對於」已知要去滑雪幾天的情形下，不會差距太多？
你有一個單一鍊結串 Linked List，每一次存取都只能從頭開始存取。現在你想要進行一連串的 m 次查找：每一次查找，你可以沿著這個鍊結串列一路走下去，而花費的時間就是你經過了幾個節點。而查找完畢以後，你唯一能做的操作就是「對於你存取過得某個節點，交換他以及他的下一個節點」。你可以重複很多次操作。請問能否設計一個線上演算法，使得經過 m 次查找以後，總花費時間與「已知未來的 m 次查找時的離線演算法」，其總時間不會差距太多？
這個是 Erik Demaine 以及 Pătrașcu 等人設計出的線上版二元搜尋樹。他們利用了 Link-Cut Tree 的概念設計出了每一次更新都不會比「最好的二元搜尋樹離線算法」差 O(log log n) 倍時間的資料結構，神猛一陣。
而競爭力分析可以追朔到在線上計算模型中的最大 Open Problem：
Conjecture:
伸展樹在所有二元搜尋樹裡頭是 O(1)-competitive 的。
解出來應該就會留名清史。
iThome鐵人賽
看影片追技術