We want to calculate $T(n)$ from recurrence relation $ T(n)= \Sigma_{i=1}^{n-1} T(i) \times T(i-1)$` and we know $T(0)=T(1)=2$. How many computation operation, an Efficient Algorithm needs for calculate $T(n)$?
a) $O(n)$
b) $O( n lg n) $
c) $ O(n \sqrt{n}) $
d) $O(n^2)$
How many terms are in the sum defining $T(n)$ as a function of $n$? You need one multiply for each, then one less adds to do the sum. The numbers $T(n)$ grow much faster-are you expected to account for that?