Is time complexity of the greedy set cover algorithm cubic?

Question

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:

1. $C \leftarrow \varnothing$
2. 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.$

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

---

EDIT

If the greedy algorithm outlined above does not have time complexity of $M^2N$, where's the flaw in estimating the computation time?

The following diagram shows the computation time per atomic operation versus the test index of 65 tests I ran my code on. The tests range from 6 sets to 1215 sets, and the values on the y-axis are computed as

$$ \text{computation time per atomic operation} = \text{cpu time used} / (M^2N). $$

From what I can tell, the assumed time complexity $M^2N$ seems to model the behavior well. Otherwise, the computation time per atomic operation wouldn't be that stable. Small values for the y-axis are either due to the computation time being too short to be measured, or if the number of elements is substantially smaller than the number of sets ($N \ll M$).

---

EDIT (Sun APR 19 2020)

This post cites exercise 35.3-3 taken from Introduction to Algorithms (3e) claiming that the (unweighted) set cover problem can be solved in time

$$ \mathcal{O}\left(\sum_{S \in \mathcal{F}}|S|\right), $$

where $S$ is a set of the problem description, and $\mathcal{F}$ are all the sets in the problem description.

Compared to the naming convention I'm using, this would mean that the problem can be solved in quadratic time $\mathcal{O}(MN)$. But how?

The algorithm still requires to find the set with the maximum number of elements involved, which requires to evaluate every set modulo the recently added one. Hence,

$$ M + (M - 1) + ... + 1 = (M + 1)M / 2, $$

which is quadratic in $M$ again.

Or is there a more efficient way to do so?

---

EDIT (Mon APR 20 2020)

My initial estimate of $\mathcal{O}(M^2N)$ does not seem to be that bad. Refering to Introduction to Algorithms (3e), page 1119, last paragraph of section A greedy approximation algorithm, it is said

a simple implementation runs in time $\mathcal{O}(|X||\mathcal{F}|\min(|X|, |\mathcal{F}|))$

where $|X|$ is the overall number of elements, and $|\mathcal{F}|$ reflects the overall number of sets.

Dividing the cpu time by this new upper bound, the variance of the time per atomic operation is clearly smaller compared to the upper bound used initially:

Answer 1

Acc. to Introductions to Algorithms (3e), given a "simple implementation" of the above given greedy set cover algorithm, and assuming the overall number of elements equals the overall number of sets ($|X| = |\mathcal{F}|$), the code runs in time $\mathcal{O}(|X|^3)$. So there are cases when the algorithm behaves cubic.