Question

Exercises 37 and 38 deal with the problem of scheduling the most talks possible given the start and end times of n talks.

Find the complexity of a brute-force algorithm for scheduling the talks by examining all possible subsets of the talks. [Hint: Use the fact that a set with n elements has ${\mathbf{2}}^{\mathbf{n}}$subsets.]

Short answer

$O\left(n^2{2}^n\right)$

Step-by-step solution

Given

We are interested in the complexity of the brute-force algorithm for scheduling the talks by examining all possible subsets of the talks.

Let us consider a set of ntalks.

Since a set of n elements has $2^n$ subsets, there are $2^n$subsets of the talks.

Find the complexity

Next, each pair of talks in a subset need to be compared to each other (to check whether they overlap or not). There are n talks and thus there are n. (n - 1) pairs of distinct talks.

We then note that we can compare at most $n\cdot (n-1)\cdot 2^n$pairs of talks and thus the worst-case complexity is $O(n\cdot n\cdot 2^n)=O\left(n^2{2}^n\right)$ (as a constant does not affect the complexity).