This section aims to investigate how the different complexities of
the two implementations reflect their experimentally measured
Figure 4.10 shows the time complexity of the
fast implementation with leftist heaps sandwiched between
. Figure 4.11 shows the experimentally established time complexity of the LMCP implementation bounded by
f3(n)=(1.3)10-7n2 and f4(n)=10-7n2. The LMCP implementation is very simple. On every iteration one pass through the working sequence is sufficient to find a local minimum compatible pair which is combined. The structure of the implementation requires one function call per iteration. The fast implementation on the other hand is very complex. In the worst case scenario there will be three priority queue operations performed on the Master Priority queue one PQInsert, one PQDeleteMin, and one PQDelete, and eight operations on the HPQs: two PQDelete, three PQMerge, two PQDeleteMin, and one PQInsert operations. The leftist tree is selected as a priority queue structure and every operation is implemented using recursive calls to the PQMerge, see Chapter 3, Section 3.6.1 for details. The depth recursion and the complexity of the algorithm, and the implementation, cause the leading coefficient of the largest term of the function f1(n), bounding the fast implementation to be 10 times higher than the leading coefficient of the largest term of function f3(n), bounding the the LMCP implementation.