So, I was going through the Rod-Cutting problem in the Dynamic Programming section of the Introduction to Algorithms by CLRS.

Here's the rod-cutting problem statement: Given a rod of length n inches and a table of prices pi for i = 1, 2,…n, determine the maximum revenue rn obtainable by cutting up the rod and selling the pieces.

Then, I saw the following pseudocode for solving this problem using top-down approach using memoization: enter image description here

In the above pseudocode, p is an array, n is an integer.

What I can't understand here is that the time complexity of this algorithm is O(n^2). I saw that reason behind this as shown in the book is following:

The running time of this procedure is O(n^2) since each subproblem is solved exactly once, and to solve a subproblem of size i, we run through i iterations of the for loop. So the total number of iterations of the for loop, over all recursive calls, forms an arithmetic series, which produces O(n^2) iterations in total.

Although I understand that the for loop in the else block will make the time complexity O(n) but I can't understand how this will form O(n^2)? Can someone please help me to understand it?

  • $\begingroup$ Let me call the second function $f(k)$ for short. To compute $f(k)$ you do $k$ iterations of the for loop. When the first function calls $f(n)$ and the recursive calls unfold, you will have $1$ run of the loop to compute $f(1)$, $2$ to compute $f(2)$, $3$ to compute $f(3)$,...,$n$ to compute $f(n)$. In total you get $1+2+3+\ldots+n=\frac{n(n+1)}{2}\in O(n^2)$. $\endgroup$ – plop Oct 4 '20 at 11:37
  • $\begingroup$ @plop I still don't get you. Can you please explain in detail? $\endgroup$ – WarWithSelf Oct 4 '20 at 12:45
  • 1
    $\begingroup$ Which part don't you understand? $\endgroup$ – plop Oct 4 '20 at 23:31

Your Answer

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

Browse other questions tagged or ask your own question.