מבני נתונים ואלגוריתמים - מחברת קורס/אלגוריתמים/נוסחאות נסיגה/תרגילים/נוסחת נסיגה לבעיית "דג הסלמון"/שאלה

$\displaystyle T(n)$ מתארת את זמן הריצה של אלגוריתם כלשהו. אנא הוכח שאם $\displaystyle T(n)=\sum _{i=1}^{n-1}[T(i)]+\Theta (n)$ אז $\displaystyle T(n)=\Omega (1.5^{n})$.

כדאי לדעת: נצטרך את פתרונה של נוסחת נסיגה זו בבעיית "דג הסלמון".