What is the time complexity of text justification algo? The following algo is a simplified version of a text justification algo taken from dynamic programming lecture notes of MIT OCW. 

I am confused why this particular algo has a time complexity of $\mathcal{O}(n^2)$ and not of $\mathcal{O}(n!)$ -:

function foo(int index) {
//some constant time operation like 2+2
       for( i = index + 1 to end ) {
           foo(i);
           }
}


Lets say end is 10.

So if foo(0) were called, the sequence of function calls would be something like this (correct me if I am wrong)-:

foo(0) = 9 calls to foo using (1 to 9)
Each foo(1) = 8 calls to foo using (2 to 9)
Each foo(2) = 7 calls to foo using (3 to 9)
and so on...


So it is $n * (n-1) * (n-2) ... * 1$ = $n!$

So shouldn't the time complexity be $\mathcal{O}(n!)$ ? Instead I find that in most cases this algorithm is represented as $\mathcal{O}(n^2)$. 

Why is that ?

The original version was of the follwing form-:

DP[i] = min{DP[j] + badness(i,j), for (j in range(i+1,n+1))}


Where badness = (page width - total width of string) ^ 3
There are two problems, here. Your foo algorithm doesn't have $\Theta(n!)$ complexity and it isn't the proper tranlation of the dynamic programming system.

foo(0) makes calls with arguments $1, 2, \dots$. The call to foo(1) makes calls with arguments $2, 3, \dots$. So now we have two outstanding calls to each of foo(2), foo(3), .... Each call to foo(2) one more call for $3, 4, \dots$, so we now have four outstanding for each of those.  Thus, foo(i) gets called $2^{i-1}$ times.  The total number of calls is $\sum_{i=1}^n 2^{i-1}=2^i-1$.

But the main problems is that your foo isn't what the dynamic programming system does. The whole point of dynamic programming is to avoid making the same recursive call many, many times. To do this, you remember the results of the function in an array, precisely so you don't have to call the function again.  You can see this in the code fragment you posted: DP[j] isn't a function call, but an array look-up.