# Runtime of weighted interval scheduling dynamic programming algorithm

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.

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