Here is the recursive CutRod algorithm:
CutRod(p, n)
if n == 0
return 0
q = -1
for i = 1 to n
q = max(q, p[i] + CutRod(p, n-i))
return qShow that the running time $T(n)$ of CutRod(p, n) is $2^n$, given
$$
T(n) = 1 + \sum_{j=0}^{n-1}T(j)
$$
We use mathematical induction. We start with the base case, considering T(0), and checking what it is equal to.
$$
\begin{align}
T(0) &= 1 + \sum_{j=0}^{0-1}T(j) \\
&= 1 \\
&= 2^0 \\
&= 2^n
\end{align}
$$
So the base case holds. Now suppose we have $T(n) = 2^n$ and consider $T(n+1)$:
$$
\begin{align}
T(n+1) &= 1 + \sum_{j=0}^{n+1-1}T(j) \\
&= 1 + \sum_{j=0}^{n}T(j) \\
&= 1 + \sum_{j=0}^{n-1}T(j) + T(n) \\
&= T(n) + T(n) \\
&= 2T(n) \\
&= 2(2^n) \\
&= 2^{n+1} \\
\end{align}
$$
Consider rod values = [1,5,7] and sought length = 3.
The greedy solution using density yields a value of 6 from <2,1>.
But the accurate CutRod bottom up solution yields a value of 7 from <3>.
Density can pose as a strong $2 \frac{1}{2}$ option, which is larger than $\frac{7}{3} = 2\frac{1}{3}$. Simply incrementing the rod length by 1 causes the density to drop too much for the greedy solution to repsect the strength of 7 at 3, here.
Here
Suppose CutRod only goes to $\lfloor n/2 \rfloor$.
CutRod needs to handle an extra base case of n == 1. $T(0)=1$, but it's never really reached. $T(1) = 1$.
CutRod's running time changes to:
$$
\begin{align}
T(n) &= T(n-1) + T(n-2) + ... + T(\lceil \frac{n}{2} \rceil) \\
&= 1 + \sum_{i= \lceil \frac{n}{2} \rceil}^{n-1} T(i) \\
&= 1 + \sum_{i=1}^{n-1}T(i) - \sum_{i=1}^{\lfloor \frac{n}{2} \rfloor}T(i)
\end{align}
$$
If the first part of this equation is thought to be $2^n$, what are we subtracting? Let's introduce $U(n)$ to be the part we subtract:
$$
\begin{align}
U(n) &= \sum_{i=1}^{\lfloor \frac{n}{2} \rfloor}T(i) \\
\end{align}
$$
After some poking around, we find if n is odd, then $U(n) = U(n-1)$ and if even, $U(n) = U(n-1) + U(n/2)$.
This function appears to be no larger than $n^2$. If we subtract $n^2$ from $2^n$, we don't overcome it. So the running time, by my estimation, doesn't appear to have changed.
MemorizedCutRodAux also needs to be adjusted to handle a base case of n == 1, in addition to n == 0. This can be p[1].
It's running time changes to be a slightly modified arithmetic series. We are performing a summation of all recursive calls. It is tempting to bound the summation from above by $\lfloor \frac{n}{2} \rfloor$, but that excludes some calls due to recursion. We squint a little to pull the factor $1/2$ out of the summation.
$$
\begin{align}
T(n) &= \sum_{i=1}^{n} \lfloor \frac{i}{2} \rfloor \\
&= \frac{1}{2} \sum_{i=1}^{n} i \\
&= \frac{1}{2} \sum_{i=1}^{n} i \\
&= \frac{1}{2} (\frac{n^2}{2} + \frac{n}{2}) \\
&= \frac{n^2}{4} + \frac{n}{4} \\
\end{align}
$$
So the running time is unchanged, at $θ(n^2)$.
Here
The code is
here
The subproblem graph for n=4 is here:
The graph has $n+1$ vertices, and $2(n-1)$ edges.
