Suppose we have n subsets $S_1, S_2, . . . , S_n$ of the set ${1, 2, \textit{…} , n}$. The a brute-force algorithm that determines whether there is a disjoint pair of these subsets is as follows below.
Based on my understanding, the algorithm starts by comparing set $S_1$ to all other sets $S_2, S_3, \textit{…}, S_n$. In the second round, it should compare $S_2$ with all other subsets $S_3, \textit{…}, S_n$, until we reach the last set and compare it with itself $S_n$.
Question 1: could you please tell me the rule of $a_i < a_j$ below in the algorithm?
Question 2: based on big-$\mathcal{O}$, the running time for comparisons is $2\times(n-1)\times (n-1)\times n$. However, I only see one comparison below in the algorithm not 2.
Best Answer
The if $a_i \lt a_j$ line is a mistake. $a_i,a_j$ are never defined and the algorithm does not need it. The $i$ loop is executed $n-1$ times, the $j$ loop is executed an average of about $\frac n2$ times, and the $k$ loop is executed $n$ times, so the number of inclusion checks is $2\cdot (n-1)\cdot \frac n2\cdot n$ with the $2$ coming from checking $S_i$ and $S_j$. We don't care about multiplicative constants. The algorithm is then $\mathcal O(n^3)$