البته دلیل اصلی کم بودن پیچیدگی همون عدم همپوشانی فضای حالت است نه کوچک بودن هزینه ترکیب.

مثال خوب این مساله هم همون فیبوناتچی است. هزینه ترکیب فیبوناتچی هم [tex]O(1) [/tex] هست ولی هزینه کلی چیز وحشتناکیه. دلیل اصلیش هم چند بار محاسبه جواب‍های مساله است. در مورد این نوع مسایل بهترین الگوریتم‍ها معمولاً الگوریتم‍های دارای حافظه مثل الگوریتم‍های پویا هستند. البته در این شرایط باید پیچیدگی حافظه رو هم محاسبه کرد. برخی اوقات پیچیدگی حافظه خودش بلای جون می‍شه!!