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$?