با استفاده از درخت بازگشت یک جواب مجانبی دقیق برای رابطه بازگشتی [tex]T(n)\: =\: T(n-a) T(a) cn[/tex] بدست آورید.
[tex]a\ge1\: ,\: c>0[/tex]
سلام
به نظر جواب دقیق مجانبی نداره!
بدترین حالت با a=1 میشه: n^2
و بهترین حالت با a=n/2 میشه: nlgn
ولی حالت معقول تر و متداولترش اینه که a را غیر وابسته به n (ثابت) بگیریم، که جواب مجانبی دقیق همون n^2 میشه.