نظریه رایانش‌پذیری: تفاوت میان نسخه‌ها

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

یک محاسبه به صورت یک تابع بازگشتی مو است، اگر دنبالهٔ تعریف شدهٔ آن، متغیرهای ورودی و یک دنبالهٔ توابع بازگشتی همراه با ورودی‌ها و خروجی‌های آن مشخص باشند؛ بنابراین اگر در تعریف دنبالهٔ بازگشتی تابع <math>f(x)</math>، توابع <math>g(x)</math> و <math>h(x,y)</math> وجود داشته باشند، در نتیجه عباراتی به شکل g(۵)=۷ و یا h(۳٬۲)=۱۰ ممکن است ظاهر شوند. در این گونه توابع، اگر آخرین عبارت مقدار تابع بازگشتی ایی که به ورودی‌ها داده شده است؛ را بدهد، محاسبات پایان می‌پذیرند.