درخت جستجوی محدود شده

اگر مجموعه قوانین شاخه شدن (branching rule) برای حل مسأله داشته باشیم که حداقل یکی از آنها به جواب برسد. به شرطی که

هر قانون شاخه شدن حداکثر b(k) شاخه می‌سازد و هر اعمال قانون شاخه شدن پارامتر را کاهش می‌دهد؛ مسأله را می‌توان در زمان O*(b(k)^k) حل کرد.

در بسیاری موارد می‌توان این کران بالا را با تحلیل بهتر بهبود داد.

(دقت کنید که b تابعی از k است.)