Results

Figure 3.10 illustrates the performance of this probabilistic scheme compared to that of the deterministic scheme. Note that the probabilistic results remain within the guaranteed factor $4$ of the corresponding deterministic results. It is interesting to note the `staircase' pattern of Figure 3.10. The sharp inflection points corresponding to the `steps' are the values of differences where the Probabilistic algorithm upgrades the value of $\overline{m}$. The computational time is almost totally dominated by the Gaussian elimination while interpolating (see [14] for details) - the vander monde matrix used has dimensions $\overline{m} * \overline{m}$ and the sharp inflection points corresponds to the algorithm `upgrading' $\overline{m}$ after an unsuccessful verification. The factoring of the polynomials is not the main computational bottleneck, even though in theory both Gaussian elimination and factoring are cubic in complexity.