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

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

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.


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$).


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.