نمایش مبدأ برای روش اکرا–بازی

در [[علوم رایانه]] '''اکرا-بازی''' روشی است برای بررسی [[پیچیدگی محاسباتی]] یک رابطه ی بازگشتی که در طراحی [[الگوریتم]] ظاهر می‌شود که تعمیمی است بر [[قضیه اصلی واکاوی الگوریتم‌ها]]. 

== فرمول == 
این روش به رابطه ی زیر اعمال می شود: 

:<math>T(x)=g(x) + \sum_{i=1}^k a_i T(b_i x + h_i(x))\qquad \text{for }x \geq x_0.</math>

که در آن:
* شرایط اولیه لازم قید شده است. 
* <math>a_i</math> و  <math>b_i</math> به ازای تمام مقادیر i ثابت هستند. 
* <math>a_i> 0</math> و <math>0 <b_i <1</math> به ازای تمام مقادیر i
* <math>\left|g(x)\right| \in O(x^c)</math> که در آن ''c'' ثابت است. 
* <math>\left| h_i(x) \right| \in O\left(\frac{x}{(\log x)^2}\right)</math> به ازای تمام مقادیر i 
* <math>x_0</math> یک ثابت است. 

رفتار حدی T(x) به صورت زیر و به ازای مقداری از ''p'' که <math>\sum_{i=1}^k a_i b_i^p = 1</math> بدست می آید: 

:<math>T(x) \in \Theta \left( x^p\left( 1+\int_1^x \frac{g(u)}{u^{p+1}}du \right)\right)</math>

== منابع ==
{{پانویس}}
*Mohamad Akra, Louay Bazzi: On the solution of linear recurrence equations. ''Computational Optimization and Applications'' '''10'''(2):195&ndash;210, 1998.

[[رده:آنالیز تقریبی]]
[[رده:رابطه‌های بازگشتی]]
[[رده:قضیه‌ها در ریاضیات گسسته]]