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

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

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

  • $\begingroup$ 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$? $\endgroup$
    – Mike B.
    May 14 '13 at 7:19
  • $\begingroup$ The running time only becomes $O(n^2)$ if you transform this recursive algorithm into a dynamic programming algorithm. $\endgroup$
    – 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.