2
$\begingroup$

Consider this implementation of a dynamic programming algorithm for weighted interval scheduling:

M-Compute-Opt(j) 
    If j=0 then 
        Return 0
    Else if M[j] is not empty then 
        Return M[j]
    Else
        Define M[j] = max(v_j + M-Compute-Opt(p(j)), M-Compute-Opt(j − 1)) 
        Return M[j]
    Endif

Here we have a set of requests $\{1, 2, \ldots , j\}$. We're assuming they're ordered by finishing time in nondecreasing order. I.e., $j$ finishes last, $j-1$ second last, etc. $v_j$ is the weight assigned to interval $j$. Also, $p(j)$ is the interval to the left of $j$ that ends as close to the beginning of $j$ as possible without overlapping. We're assuming these were also computed beforehand.

The textbook I'm looking at says the runtime is $O(n)$ because a single call to M-Compute-Opt is $O(1)$ and we call it twice for every empty entry in array M. I almost buy it except it seems to me that we could end up calling it more often for some $i \in \{1, \ldots , j\}$ if the function $p$ maps lots of elements to that $i$. For example, if there is some interval $i$ where right after it ends a ton of intervals start, $p$ would map lots of intervals to it. And of course M-Compute-Opt wouldn't be called from within those instances since the value would be stored the first time, but it seems they would run nonetheless.

I guess in general I understand the argument given in the book, but I was wondering if there is a good one way to understand the linear time from a more intuitive standpoint. I'm not used to calculating runtimes and I feel like if I saw a different problem like this one I wouldn't come up with the "trick" used.

$\endgroup$

2 Answers 2

0
$\begingroup$

If I understand your concern correctly, you are right in that many $p(j)$ may give the same $i$. But that means that other $i$s don't get many $p(j)$s (the total of them is $n$).

$\endgroup$
0
$\begingroup$

The solution you sketched is using recursion with memoization. One of the reasons to prefer dynamic programming over recursion is because it is much simpler to analyze. Let us analyze the running time of the following snippet (the recusive function is the same as yours, I just renamed it opt):

def opt(j):
    if j == 0:
        return 0
    elif M[j] is not None:
        return M[j]
    else:
        M[j] = max(v_j + opt(p(j)), opt(j - 1))
        return M[j]


for i in range(n + 1):
    opt(i)

print(opt(n))

Observe that it first calls opt(0), which is the base case, which is constant time. Now, opt(1) results in two recursive calls, both being opt(0). But this we know is two calls, each with constant time complexity.

Now, consider any j in the for-loop. Since every smaller j' is already computed, when we call opt(j), the two values opt(p(j)) and opt(j-1) corresponds to a single lookup in M. Hence to compute opt(j) when we already have all smaller values, we need only constant time.

It follows that the entire body above runs in time $O(n)$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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