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