Applying Data Mining to Define TSP Asymptotic Time Complexity

Computational science is often referred to as the third science,complementing both theoretical and laboratory science. In this field, new challenges are continuously arising. The asymptotic time complexity definition of both deterministic and non-deterministic algorithms to solve all kinds of problems is one of the key points in computer science. Knowing the limit of the execution time of an algorithm when the size of the problem goes to infinity is essential. In particular, data-dependent applications is an extremely challenging problem because for a specific issue the input data sets may cause variability in execution times. The development of an entire approach to define the asymptotic time complexity of a hard data-dependent parallel application that solves the traveling salesman problem (TSP) is the focus of this study. Two different parallel TSP algorithms are presented. One of these is used to show the usefulness and the profits of the proposed approach, and the other one is used as witness. The experimental results are quite promising.