روابطی که در تعریفشان از خودشان استفاده می‌شود، روابط بازگشتی نام دارند. مثلاً فیبوناچی یک رابطه بازگشتی می‌باشد. بسیاری از الگوریتم‌ها نیز به صورت بازگشتی مسئله را حل می‌کنند و از این رو تحلیل زمانی الگوریتم‌هایی که زمان اجرای آن‌ها بر اساس یک تابع بازگشتی مشخص می‌شود اهمیت پیدا می‌کند. الگوریتم‌هایی مانند مرتب سازی ادغامی از این دسته الگوریتم‌ها می‌باشند. برای این کار دو روش متداول وجود دارد.

با توجه به این که در اکثر اوقات در تلاشیم تا زمان اجرای الگوریتم از میزان مشخصی بیشتر نباشد حدس زدن اردر الگوریتم و سپس اثبات آن به کمک استقراء می‌تواند راه حل مناسبی باشد. دقت کنید که در این روش تنها یک تخمین دسته بالا برای الگوریتم به دست آمده است و ممکن است اردر الگوریتم در واقعیت کمتر باشد. برای مثال سعی می‌کنیم تا اردر رابطه زیر را بدست آوریم:

$$T(2n)=2T(n) +2n -1 , T(2) = 1$$

در این رابطه که تنها برای توان‌های دو تعریف شده است هزینه‌ی هر یک از توان‌های دو بر اساس مقدار قبلی به دست می‌آید. ابتدا آن را به حالت کلی زیر می‌نویسیم: $$T(g(n)) = E(T,n), E(T,n) = 2T(n)+2n-1, g(n)=2n$$

حال باید حدسی مانند $f(n)$ زده و اثبات کنیم که $T(n)\leq f(n)$ . برای این اثبات لازم است که در $f(n)$، $g(n)$ را به جای $n$ قرار دهیم و سپس در $E$ ، $f(n)$ را جایگزین $T(n)$ کنیم. سپس باید نشان دهیم $f(g(n))$ از مقداری که جایگزین $E(T,n)$ شده است، کوچک‌تر نیست یعنی: $$f(g(n)) \geq E(f,n)$$

شهود رابطه بالا اینگونه است: ما می‌خواهیم ثابت کنیم $f(n)$ بسیار سریع‌تر از $T(n)$ رشد می‌کند. بنابراین اگر در $f(n)$ و $T(n)$، $g(n)$را به جای $n$ جایگزین کنیم، مقدار $f(n)$ از $T(n)$ بزرگتر خواهد شد. حال برای مثالی که زدیم اگر حدسمان را $f(n)= n \log_2 n$ در نظر بگیریم، باید نشان دهیم: $$(2n)(log_2 2n) \geq 2(nlog_2 n) + 2n -1$$ با اصلاح تابع به

$f(n) = 2 n\log_2 n$ تساوی بالا برقرار می‌شود. دقت کنید که در طی مراحل اثبات نمی‌توانیم از نمادگذاری $O$ استفاده کنیم زیرا در طی مراحل مختلف ثابت‌های مختلفی وجود دارند که لزوماً با هم برابر نیستند و از آن‌ها نمی‌توان چشم پوشی کرد.

الگوریتم‌های متعددی وجود دارند که از ایده استقرایی تقسیم و حل برای حل مسئله استفاده می‌کنند. تحلیل زمانی این الگوریتم‌ها را می‌توان به کمک قضیه مستر انجام داد. به طور کلی فرض می‌کنیم تابع زمان حل مسئله به شکل زیر باشد: $$T(n)=aT(\frac{n}{b})+cn^k , a \geq 1 , b > 1$$ یعنی هر نمونه از مسئله به $a$ مسئله دیگر که اندازه هر کدام $\frac{1}{b}$ مسئله اصلی باشد تقسیم می‌شود و ادغام این مسائل $cn^k$ هزینه می‌برد. در این صورت بسته رابطه بین $a$ و $b^k$ اردر الگوریتم مشخص می‌شود:

• حالت $a>b^k$:

در این حالت هزینه ادغام نسبت به هزینه تقسیم و حل ناچیز می‌شود: $$T(n)=O(n^{\log_b^a})$$

• حالت $a=b^k$:

در این حالت هزینه ادغام با هزینه تقسیم و حل برابری می‌کند: $$T(n)=O(n^k \log n)$$

• حالت $a<b^k$:

در این حالت هزینه تقسیم و حل نسبت به هزینه ادغام ناچیز است و عملاً ادغام زیرمسئله‌های مسئله اصلی هزینه اصلی را دربردارد: $$T(n)=O(n^k)$$

سعی می‌کنیم تا الگوریتم مرتب سازی ادغامی را به کمک این روش تحلیل کنیم: $$T(n)=2T(\frac{n}{2})+n$$ در این حالت $a=2,b=2,=k=1$ می‌باشد و نامساوی $a=b^k$ برقرار است بنابراین: $$T(n)=O(n^1 \log n) = O(n\log n)$$

• طراحی الگوریتم با رویکردی خلاقانه - یودی منبر - ترجمه‌ی احمد صادقی صفت و سید علی حسینی
• قضیه مستر - ویکی‌پدیا