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

• Please ask only one question per post. Dec 16, 2016 at 9:34
• I think they are related, so I put them together. Dec 16, 2016 at 9:43

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