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:
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?
forloop. 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