Running time of greedy scheduling algorithm Here is an algorithm to output a subset of activities S such that no activities in S overlap and profit(S) is maximum.

Define $p[i]$ to be the largest index $j$ such that $a_j$ does not overlap $a_i$.

$\#$ Return maximum possible profit from $a_1,...,a_n$

def rec_opt(n):
    if n == 0:
        return 0
    else:
        return max(rec_opt(n-1), w_n + rec_opt(p[n]))


It doesn't mention what $w_n$ is in the slide, but I think it is the profit of the activity $a_n$.


  Consider a set of $n$ activities where there is no overlap at all. Then $T(n) = 2T(n − 1) + c$. This recurrence has an exponential closed-form, $O(2^n)$.



"return max(rec_opt(n-1), w_n + rec_opt(p[n]))": I think this line takes time $2T(n-1)$.
"if n == 0": this line takes time $c$.


Am I correct?

One more question, how can we get $O(2^n)$ from $T(n) = 2T(n − 1) + c$?
You are asking several questions. I will only answer the second one.

Suppose that $T(n) = 2T(n-1) + c$, and that $T(0) = a$. Define $S(n) = T(n) + c$. Then $S(n) = T(n)+c = 2T(n-1)+2c = 2S(n-1)$, and so $S(n) = 2^nS(0) = 2^n(a+c)$. We conclude that $T(n) = 2^n(a+c)-c = 2^na+(2^n-1)c$.