Runtime of weighted interval scheduling dynamic programming algorithm

Question

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.

Answer 1

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