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.