1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Is it the full version of the function foo? If no, could you post the full version? $\endgroup$ – fade2black Sep 1 '17 at 8:35
  • $\begingroup$ @fade2black It was given in a mathematical form. So no real code. $\endgroup$ – ng.newbie Sep 1 '17 at 8:36
  • $\begingroup$ @fade2black see my edited question $\endgroup$ – ng.newbie Sep 1 '17 at 8:42
2
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

This pseudo code is recursive version of the problem, as you said in mathematical form. This is definitely not $O(n^2)$. Note that you compute $DP(i)$ more than once which is known as overlapping problems. That's why the time complexity grows very fast.

What you need is compute $DP(i)$ only once for each $i$ storing them in a table. This is the gist of DP. In your case, given $n$, you have to compute $DP[n]$, then compute $DP[n-1]$ using $DP[n]$, then $DP[n-2]$ using $DP[n-1]$ and $DP[n]$, and so on. Since $1+2+\dots + n = \frac{(n+1)n}{2}$, its complexity is $O(n^2)$.

Example: for $n = 4$

$DP[4] = 0$

$DP[3] = \min \{DP[4] + badness(3,4)\} = \min\{ 0 + badness(3,4)\} = badness(3,4)$

$DP[2] = \min \{DP[3] + badness(2,3), DP[4] + badness(2,4)\} = \min\{badness(3,4)+badness(2,3), badness(2,4)\}$

$DP[1] = \min\{DP[2] + badness(1,2), DP[3] + badness(1,3), DP[4] + badness(1,4)\} = \{\dots\}$

$\endgroup$
  • $\begingroup$ So you mean to say the memoized algorithm will be of $\mathcal{O}(n^2)$ ? $\endgroup$ – ng.newbie Sep 1 '17 at 8:56
  • $\begingroup$ yes. doesnt the source provide the DP version? $\endgroup$ – fade2black Sep 1 '17 at 8:58
  • $\begingroup$ But I don't see in your definition the base step of the recursion. $\endgroup$ – fade2black Sep 1 '17 at 9:01
  • $\begingroup$ The base case is suppose to be $DP[4] = 0$ or $DP[n] = \phi$ $\endgroup$ – ng.newbie Sep 1 '17 at 12:10
  • $\begingroup$ @ng.newbie You should add it to the recursive formula in your OP as $DP[n] = 0$. In any case that does not change my answer, it can be computed using DP as I described in my answer, that takes $O(n^2)$ time. $\endgroup$ – fade2black Sep 1 '17 at 17:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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