I claim that the greedy algorithm for solving the set cover problem given below has time complexity proportional to $ M^2N$ , where $ M$ denotes the number of sets, and $ N$ the overall number of elements.

Question: true or false?

**Approximation Algorithms**, Vazirani, 2001, 1e, p.16, Algorithm 2.2:

- $ C \leftarrow \varnothing$
- While $ C \neq U$ do Find the set whose cost-effectiveness is smallest, say $ S$ .
Let $ \alpha = \frac{c(S)}{|S – C|}$ , i.e., the cost-effectiveness of $ S$ .

Pick $ S$ , and for each $ e \in S – C$ , set $ \text{price}(e) = \alpha$ .

$ C \leftarrow C \cup S.$

- Output the picked sets.

In the first iteration, the cost-effectiveness of $ M$ sets have to be computed.

In the second iteration, the cost-effectiveness of $ M-1$ sets have to be computed.

Since everything between $ 1$ and $ M$ iterations may be needed to find the sets that cover all elements, in the mean it may be $ M/2$ iterations.

I.e. in the worst case we need to compute $ M + (M-1) + (M-2) + … + 1 = M(M+1)/2$ times the cost effectiveness.

Determining cost-effectiveness requires the computation of a difference which has time complexity proportional to the number of elements.

Hence, the time complexity is dominated by the term $ M^2N$ .