Break Even Point

This section is concerned only with the time complexity of the Combination phase. The other two phases, Level Assignment and Reconstruction, are shared between the algorithms and the implementations, thus are excluded from the timing experiments^4.1. The break even point between the two implementations, the Fast Implementation with leftist heaps (FILH) and the Combination using local minimum compatible pairs (LMCP), occurs while building OABST for a small number of input elements. To lower the error introduced by the getrusage system call, when very small times are measured, the time measurement is performed as follows. The function building the tree in phase I is called 100 times in a loop. The total time it takes to build 100 trees (which are identical because the same input data set is used 100 times) is measured and normalized. Ten different random number sequences are sampled, and the time measurements are averaged. The data in Figure 4.1 reflects the user and system time (seconds) as reported by getrusage system call. Every time measurement represents the arithmetic mean: $\frac{1}{10}{(\sum_{i=1}^{10}TotalTime_{forBuilding 100 Trees})}$

The advantage of the LMCP implementation is insignificant and is observed only for very small size input sequences (See Figures 4.1 and 4.2). The LMCP implementation marginally outperforms the FILH for the input data sizes between 2 and 400 nodes. Any practical usage of large OABST will need a fast implementation to build it.

  

Figure 4.1: Time complexity (seconds) of the two implementations of the Combination phase for data sets between 50 and 1,000 nodes. Fast implementation with leftist heaps (FILH), implementation with combination of l.m.c.p (LMCP)

.

  

Figure 4.2: Break even point between the two implementations occurs for input sequence of 400 nodes.

Footnotes

... experiments^4.1

Section 4.3 discusses the time complexity of all three phases of the Hu-Tucker algorithm.