Experimental Time Complexity vs. Theoretical Time Complexity

  

Figure 4.10: Comparison of the theoretical and experimental time complexity of the fast implementation.

  

Figure 4.11: Comparison of the theoretical time complexity of the Combination phase with l.m.c.p.

This section aims to investigate how the different complexities of the two implementations reflect their experimentally measured time complexities. Figure 4.10 shows the time complexity of the fast implementation with leftist heaps sandwiched between $f_1(n)=(4.8)10^{-6}n \lg n$ and
$f_2(n)=(4)10^{-6}n \lg n$. Figure 4.11 shows the experimentally established time complexity of the LMCP implementation bounded by
f₃(n)=(1.3)10^-7n² and f₄(n)=10^-7n². 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 f₁(n), bounding the fast implementation to be 10 times higher than the leading coefficient of the largest term of function f₃(n), bounding the the LMCP implementation.