# Confusion related to calculating time complexity

I have some confusion related to calculating the time complexity of this algorithm

opt(i)
for j=i:n
a = f(i,j) + opt(j+1)
end


How is the running time of this algorithm $O(n^2)$?

• The question isn't entirely clear to me. Currently, the posed function depends on 2 variables ($i$ and $n$). With what parameter is opt initially called? And whats the time complexity of $f$? – Mike B. May 14 '13 at 7:19
• The running time only becomes $O(n^2)$ if you transform this recursive algorithm into a dynamic programming algorithm. – JeffE May 15 '13 at 2:23

Let $T(i)$ be the running time of opt(i) then we have $$T(i)= \sum_{k=i}^n T(k+1).$$ You have not specified a recursion anchor, but I guess it is something like $T(n+1)=1$. Write down the series $T(n),T(n-1),T(n-2),\dots$ and you get the impression that $T(i)=2^{n-i}$. This guess can be proven by induction, since assuming that $T(i)=2^{n-i}$, we have $$T(i-1)= \sum_{k=i-1}^n T(k+1)= T(i)+\sum_{k=i}^n T(k+1)= 2 T(i) = 2^{n-(i-1)} .$$
Thus, $T(0)= 2^n$ and therefore it is not in $O(n^2)$.
PS I assumed that in the recursion the value of opt is never stored and will always be recomputed.