3
$\begingroup$

I decide to learn more about dynamic programming, so I started reading the Dynamic Programming chapter from the CLSR book.

The first example problem presented there is Rod Cutting (15.1). Given a rod of length n and a list of prices for rods of any sizes figure out how to cut the rod so that the price of the pieces will be maximized (and one can only cut at even positions).

The first recursive algorithm presented there is the following

CutRod(p, n) 
  if n == 0
    return 0
  q = -inf
  for i = 1 to n
    q = max(q, p[i] + CutRod(p, n -1))
  return q

n is the size of the rod and p an array that contains the prices.

I understand the algorithm, the problem I have is that I thought intuitively the time complexity of such an algorithm would be O(b^d) (where b is the branching factor and d the depth of the recursion tree) which would be O(n^n).

In the book the recurrence relation is presented: T(0) = 1 and T(n) = 1 + sum(j=0, n-1, T(j)) Then it is explained that the complexity following from this is O(2^n) which you can easily be seen by expand the recurrence relation.

How can I quickly see that my initial intuition was wrong? And in general when looking at a recursive algo how can I figure out weather the time complexity is O(b^d) or not.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

Based on the code you show there, your intuition is right.

However, it looks like there is a typo in the code and the next-to-last line should have been

  q = max(q, p[i] + CutRod(p, n-i))

i.e., n-i rather than n-1. Try to work through a proof of correctness, or through a few examples, to see why I say that. The running time analysis they show is for the corrected code, rather than the code with the typo, and then once you make that correction to the code, the recurrence relation they provide is correct.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Yes there is a typo! But it should be n - i (since I iterate over i and not j). Thanks! $\endgroup$
    – Nils
    Commented Jun 10, 2018 at 12:23
  • $\begingroup$ The branching factor gets reduced by 1 at every recursive call, therefore it is not O(n^n). $\endgroup$
    – Nils
    Commented Jun 10, 2018 at 12:44
  • 1
    $\begingroup$ @Nils, oops! Thanks, fixed. Yes, I know the branching factor gets reduced by one in the corrected code, so the corrected code doesn't run in $\Theta(n^n)$. What I'm saying is that the uncorrected code (with the typo; as shown in your question) does have $\Theta(n^n)$ running time (its branching factor is always $n$). In contrast, for the corrected code (with the correction shown in my answer), the running time is not $\Theta(n^n)$; rather, it follows the recurrence $T(n) = O(1) + T(n-1) + T(n-2) + \cdots + T(1)$ (the recurrence you mention in the question). $\endgroup$
    – D.W. ♦
    Commented Jun 10, 2018 at 17:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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