قضیه اصلی واکاوی الگوریتم ها

قضیه اصلی واکاوی (تحلیل) الگوریتم ها که حالتی خاص از روش اکرا-بازی است در تحلیل الگوریتم ها، یک راه حل سرراست برای حالت های مجانبی که در عمل در انواع روابط بازگشتی رخ می دهند، ارائه می کند. این قضیه با کتاب درسی معروف مقدمه ای بر الگوریتم ها نوشتهٔ کرمن، لیسرسن، ریوست و استین به شهرت رسید. این قضیه در بخش ۴٫۳ دراین کتاب معرفی شده است و متعاقباً در بخش ۴٫۴ به اثبات رسیده است. هرچند که نمی توان تمامی روابط بازگشتی را به کمک قضیهٔ اصلی حل کرد.
a تعداد زیرمسئله هاست.
n/b اندازهٔ هر یک از زیرمسئله هاست. (در اینجا فرض شده است که اندازهٔ همهٔ زیرمسئله ها با هم برابر است.)
(f(n هزینهٔ بخش غیر بازگشتی است که شامل هزینهٔ تقسیم مسئله به زیرمسئله ها و هزینهٔ ادغام پاسخ به زیرمسئله هاست.
قضیهٔ اصلی روابطی را مورد بررسی قرار می دهد که به شکل زیر باشند:
T ( n ) = a T ( n b ) + f ( n ) where a ≥ 1 ,  b > 1. {\displaystyle T(n)=a\;T\!\left({\frac {n}{b}}\right)+f(n)\;\;\;\;{\mbox{where}}\;\;a\geq 1{\mbox{, }}b>1.}
در استفاده از رابطهٔ فوق برای یک الگوریتم بازگشتی معنای علائم به کار رفته، به شرح زیر است: *n اندازهٔ مسئله است.