Time Complexity: Intuition for Recursive Algorithm

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.

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.

StackExchange Computer Science Q#92859, answer score: 2