7.8

Consider the algorithm in Figure 7.18 to compute \(\alpha^+\). Show that this algorithm is more efficient than the one presented in Figure 7.8 (Section 7.4.2) and that it computes \(\alpha^+\) correctly.


The algorithm is correct because:

To see that this algorithm is more efficient than the one presented in the chapter, note that we scan each FD once in the main program. The resulting array appears has size proportional to the size of the given FDs. The recursive calls to addin result in processing linear in the size of appears. Hence the algorithm has time complexity which is linear in the size of the given FDs. On the other hand, the algorithm given in the text has quadratic time complexity, as it may perform the loop as many times as the number of FDs, in each loop scanning all of them once.